자료구조란?

자료구조(Data Structure)

• 데이터 단위와 데이터 자체 간의 물리적 또는 논리적 관계
• 프로그램이 데이터를 표현하는 부분과 그렇게 표현된 데이터를 처리하는 부분으로 구성되어 있다고 정의할 때, '데이터의 표현'을 담당하는 부분에 해당

자료구조의 종류 개괄

선형 자료구조(Linear Data Structure)

• 데이터를 일렬로 저장하는 구조
• 리스트, 스택, 큐 등

비선형 자료구조(Non-Linear Data Structure)

• 데이터를 일렬로 저장하지 않는 구조
• 트리, 그래프, 해시 테이블 등

자료구조와 알고리즘

• 알고리즘은 자료구조에 의존적
  : 자료구조가 결정되어야 그에 따른 효율적인 알고리즘을 결정할 수 있기 때문

---

알고리즘의 성능 분석 방법

시간복잡도와 공간복잡도

시간 복잡도(Time Complexity)

• 알고리즘이 특정한 상황에서 연산을 수행하는 속도
• 알고리즘의 성능 평가 시 일반적으로 사용되는 지표

공간 복잡도(Space Complexity)

• 알고리즘이 특정한 상황에서 연산을 수행하기 위해 필요로 하는 메모리 용량

시간 복잡도의 분석과 표현

• 처리해야 할 데이터의 개수 $n$에 관한 연산횟수를 나타내는 $T(n)$을 구하는 방식으로 시간복잡도 계산 수행
• 빅-오 표기법으로 표현
  : 시간복잡도 함수 $T(n)$의 최고차항의 차수로 표기
• 시간복잡도 계산 시 최선의 경우, 평균적인 경우, 최악의 경우를 고려
  : 대부분 최악의 경우를 기준으로 알고리즘의 성능을 측정

시간복잡도 계산의 기준

최악의 경우(worst case)

• 탐색 대상이 되는 데이터를 모두 탐색했을 때의 시간복잡도
• 프로그램 실행 시간의 상한선
• 알고리즘 성능 평가 지표로 사용
  : 데이터의 개수가 많아질수록 알고리즘별 연산 횟수의 차이가 극명해지고,
  시간복잡도 계산이 쉽기 때문

최선의 경우(best case)

• 탐색을 수행한 데이터의 개수가 가장 적을 때의 시간복잡도
• 프로그램 실행 시간의 하한선

평균적인 경우(average case)

• 데이터의 총 개수가 $n$이고 알고리즘 수행 과정에서 탐색한 데이터가 $x$개일 때,
  탐색한 데이터 개수별 연산 횟수 $f(x)$의 기댓값
• $T(n)=\sum_{x=1}^{x=n}f(x)p(x)$
  ( $p(x)$ = 알고리즘 수행 시 탐색한 데이터가 $x$개일 확률)
• "평균"을 정의하기가 까다롭고, 복잡한 알고리즘의 시간복잡도 계산이 까다로움

빅-오 표기법(Big-O Notation)

개념 정리

• 데이터가 $n$개일 때의 시간복잡도 함수 $T(n)$에서 가장 영향력이 큰 부분을 기준으로 시간복잡도를 나타내는 방식
• 시간복잡도 함수 $T(n)$의 최고차항의 차수로 표기

대표적인 빅-오 표기(성능순으로 나열)

$O(1)$ / 상수형 빅-오

• 데이터의 개수에 관계없이 연산 횟수가 일정한 알고리즘

$O(logn)$ / 로그형 빅-오

• 데이터 개수의 증가율에 비해 연산 횟수의 증가율이 매우 낮은 알고리즘

$O(n)$ / 선형 빅-오

• 데이터 개수와 연산 횟수가 비례하는 알고리즘

$O(nlogn)$ / 선형로그형 빅-오

• 데이터의 개수가 배로 증가할 때, 연산 횟수는 O(n)일 때보다 약간만 증가하는 알고리즘

$O(n^2)$

• 데이터의 개수가 증가할 때, 연산 횟수는 그 제곱만큼 증가하는 알고리즘
• 중첩된 반복문을 사용하는 알고리즘에 해당

$O(n^3)$

• 삼중 반복문을 사용하는 알고리즘에 해당

$O(2^n)$ / 지수형 빅-오

• 데이터 개수가 증가할 시 연산 횟수가 기하급수적으로 증가하는 알고리즘
• 이 이상의 시간복잡도를 보일 경우, 성능 개선이 필요한 알고리즘에 해당

---

Reference

• 윤성우의 열혈 자료구조 (윤성우 저, 오렌지미디어 출판)