알고리즘의 시간 복잡도 총 정리

무거운 프로그램일 수록 처리하는 데이터가 많아지고 처리하는 작업이 복잡해질수록 시간은 매우 중요해집니다. 그래서 개발자들은 상황에 따라 특정 알고리즘을 유연하게 사용할 수 있어야 합니다.

 

 

특정 알고리즘의 실행시간을 표기하는 용어는 아래와 같습니다.

 

Big O 표기법에서 O 는 "on the order of"의 약자로 "~만큼의 정도로 커지는" 것이라고 해석됩니다. O(n)은 n만큼 커지는 것이므로 n이 늘어날수록 선형적으로 증가하게 됩니다. O(n/2)는 n이 무한대로 커지면 1/2는 결국 의미가 없어지므로 O(n)과 같은 의미로 볼 수 있습니다.

 

Big Ω표기법은 반대로 알고리즘 실행시간의 하한을 나타낸 것입니다. 예를 들어 선형 검색은 n개의 항목이 있을 때 앞에서부터 차례로 하나씩 검색하므로 총 n번을 검색하게 됩니다. 따라서 선형검색의 상한은 O(n)이 되지만 운이 좋다면 1번만에 검색을 끝낼 수 있으므로 하한은 Ω(1)가 됩니다.
용어를 다시 한 번 정리해볼까요?

 

 

Big O (빅 오) - 최악의 경우, 알고리즘 실행시간의 상한

Big Ω (빅 오메가) - 최선의 경우, 알고리즘 실행시간의 하한

Big θ (빅 세타) - O와 Ω가 같은 경우