[CS50] 알고리즘: 알고리즘 표기법
❄️ David Malan 교수의 모두를 위한 컴퓨터 과학(CS50 2019)을 바탕으로 정리한 내용입니다.
아래는 알고리즘을 실행하는데 걸리는 시간을 표현한 것입니다.
위와 같은 그림을 공식으로 표기한 것이 Big O 표기법입니다.
여기서 O는 “on the order of”의 약자로, 쉽게 생각하면 “~만큼의 정도로 커지는” 것이라고 볼 수 있습니다.
O(n) 은 n만큼 커지는 것이므로 n이 늘어날수록 선형적으로 증가하게 됩니다.
O(n/2)도 결국 n이 매우 커지면 1/2은 큰 의미가 없어지므로 O(n)이라고 볼 수 있습니다.
주로 아래 목록과 같은 Big O 표기가 실행 시간을 나타내기 위해 많이 사용됩니다.
아래로 갈 수록 더 빠른 알고리즘입니다.
Big O가 알고리즘 실행 시간의 상한을 나타낸 것이라면, 반대로 Big Ω는 알고리즘 실행 시간의 하한을 나타내는 것입니다.
예를 들어 선형 검색에서는 n개의 항목이 있을때 최대 n번의 검색을 해야 하므로 상한이 O(n)이 되지만 운이 좋다면 한 번만에 검색을 끝낼수도 있으므로 하한은 Ω(1)이 됩니다.
역시 아래 목록과 같은 Big Ω 표기가 많이 사용됩니다.
생각해보기
실행시간의 상한이 낮은 알고리즘이 더 좋을까요, 하한이 낮은 알고리즘이 더 좋을까요?
- 가장 최적의 상황에 걸리는 시간이 적게 걸리는 것(=하한이 낮음)도 중요하지만,
- 가장 최악의 상황을 가정했을 때 실행시간이 적거나(=상한이 낮음) 평균적으로 실행시간이 더 적게 걸리는게 알고리즘이 더 좋은 알고리즘이라고 생각합니다.
💛 개인 공부 기록용 블로그입니다. 👻