CS 부수기 - 시간 복잡도 편

시간 복잡도

---

자료 구조를 공부하면 빼놓을 수 없는 부분이 시간 복잡도이다.

자료 구조에서 자료의 삽입, 삭제, 탐색을 위한 시 / 공간적 소요량 혹은 알고리즘에서의 성능 분석에 많이 사용된다.

일반적으로 큰 영역으로는 복잡도라고 부르며, 크게 시간 복잡도(Time Complexity)와 공간 복잡도(Space Complextiy)로 나눠진다.

정의는 다음과 같다.

시간 복잡도 : 입력과 문제를 해결하는데 걸리는 시간 사이의 함수 관계

공간 복잡도 : 프로그램이 실행 시에 필요로 하는 자원 공간의 양

일반적으로는 시간 복잡도를 많이 요구하는 편이다. 시간은 금이기 때문에

시간 복잡도를 표기하는 방법은 대표적으로 다음 세 가지가 있다.

Big-O : 상한 점근, 일반적으로 최악의 경우
Big-Ω : 하한 점근, 일반적으로 최선의 경우
Big-Θ : 상한 점근과 하한 점근의 평균, 최악과 최선의 평균

그리고, 일반적인 시간 복잡도에서의 표기 방법은 Big-O 표기법을 주로 사용한다.
최악의 경우에서 가장 많은 시간이 소요되는 경우를 찾기 때문이다.

그렇다면 각 자료 구조에서의 시간 복잡도는 다음 표를 참고하면 된다.

자료 구조	삽입	삭제	탐색
배열 (Array)	O(n)	O(n)	O(n)
스택 (Stack)	O(n)	O(1)	O(1)
큐 (Queue)	O(n)	O(1)	O(1)
링크드 리스트 (Linked List)	O(n)	O(1)	O(1)
더블 링크드 리스트 (Double Linked List)	O(n)	O(1)	O(1)
이진 탐색 트리 (Binary Search Tree)	O(log n)	O(log n)	O(log n)
AVL 트리	O(log n)	O(log n)	O(log n)

Adios.