Intro
우리가 프로그램을 작성한 후에 실행하면 작업이 완료될때까지 어느정도 시간이 소요됩니다.
아주 간단한 프로그램인 경우에는 실행 시간을 걱정할 필요가 없지만, 처리하는 데이터가 많아지고 처리하는 작업이 복잡해질수록 실행 시간은 매우 중요해집니다.
특정 알고리즘을 작성하였을 때 그 실행 시간을 표기하는 방법을 배워보겠습니다.
위와 같은 그림을 공식으로 표기한 것이 Big O 표기법입니다.
여기서 O는 “on the order of”의 약자로, 쉽게 생각하면 “~만큼의 정도로 커지는” 것이라고 볼 수 있습니다.
O(n) 은 n만큼 커지는 것이므로 n이 늘어날수록 선형적으로 증가하게 됩니다. O(n/2)도 결국 n이 매우 커지면 1/2은 큰 의미가 없어지므로 O(n)이라고 볼 수 있습니다.
주로 아래 목록과 같은 Big O 표기가 실행 시간을 나타내기 위해 많이 사용됩니다.
O(n^2)
O(n log n)
O(n) - 선형 검색
O(log n) - 이진 검색
O(1)
Big O가 알고리즘 실행 시간의 상한을 나타낸 것이라면, 반대로 Big Ω는 알고리즘 실행 시간의 하한을 나타내는 것입니다.
예를 들어 선형 검색에서는 n개의 항목이 있을때 최대 n번의 검색을 해야 하므로 상한이 O(n)이 되지만 운이 좋다면 한 번만에 검색을 끝낼수도 있으므로 하한은 Ω(1)이 됩니다.
역시 아래 목록과 같은 Big Ω 표기가 많이 사용됩니다.
Ω(n^2)
Ω(n log n)
Ω(n) - 배열 안에 존재하는 값의 개수 세기
Ω(log n)
Ω(1) - 선형 검색, 이진 검색
