시간복잡도

시간복잡도(Time Complexity)는 알고리즘의 효율성을 판단하기 위한 지표로서, 프로그램 수행에 걸리는 절대적 시간이 나닌 알고리즘을 수행하는데 사용되는 연산들이 몇 번 이루어지는가에 대한 것을 상대적 지표로 나타낸 것이다.

 

시간복잡도에 사용되는 표기법은 Big-O(상한 점근, 최악의 경우를 나타낸다.), Big-Omega(하한 점근, 최선의 경우를 나타낸다.), Theta(그 둘의 평균)가 있다.

가장 자주 사용되는 표기법은 Big-O 표기법으로, 최악의 경우를 고려한다. 즉, '최소한 특정 시간 이상이 걸린다'가 아닌 '이정도 시간까지 걸릴 수 있다'를 고려한다.

 

Heap의 시간복잡도

 

정렬의 시간복잡도

 

자료구조의 시간복잡도