[자료구조] 자료구조의 개요

자료구조의 필요성

• 데이터 효과적으로 저장, 처리하는 방법에 대한 이해 필요
• 불필요한 메모리 및 성능 낭비를 피하기 위해

기본적인 자료구조

1. 선형 구조
   • 배열
   • 연결리스트
   • 스택
   • 큐
2. 비선형 구조
   • 트리
   • 그래프

자료구조와 알고리즘

• 효과적인 자료구조 설계를 위해 알고리즘 지식 필요
• 효과적인 알고리즘 작성을 위해 적절한 자료구조 사용

성능 측정 방법론

1. 시간 복잡도 : 사용되는 연산 횟수
   • Big-O 표기법 사용하며, 최악의 경우를 나타냄
   • O(n) ← n 만큼 반복
   • O(n²) ← 이중 for문을 사용해서 n의 2제곱만큼 반복됨
   • O(1) ← 한번에 처리됨  
   • O(1) → O(n) → O(nlogn) → O(n²) → O(n³)  (순서대로 1000 → 1,000,000 → ... → ...→ 10억번 연산(1초 이상 소요))
   • 시간복잡도를 표기할 땐 항상 큰 항과 계수만 표기 ex. O(3n**2 + n) = O(n**2) 2)
2. 공간 복잡도 : 사용 되는 메모리의 양
   • MB 단위로 표기 ex. int는 4byte → a[1000] = 4KB, int a[1000000] = 4MB

 

 

 

참고 |  fast campus 컴퓨터공학 전공 필수