CS50 2019 강의를 듣고 내용을 정리한 시리즈 글입니다.
학습목표
알고리즘의 실행 시간의 상한과 하한을 표기할 수 있습니다.
핵심 단어
- Big O
- Big Ω
강의 내용
1. Big O
알고리즘 실행 시간의 상한을 나타낸다.
주로 아래 목록과 같은 Big O 표기가 실행 시간을 나타내기 위해 많이 사용된다.
- O(n^2)
- O(n log n)
- O(n)
- O(log n)
- O(1)
실행 시간은 O(1) ~ O(n^2) 순이다.
저번 시간에 정리했던 선형 검색과 이진 검색의 경우 각각 O(n)과 O(log n)의 실행 시간을 가진다.
2. Big Ω
알고리즘 실행 시간의 하한을 나타낸다.
예를 들어 선형 검색에서는 n개의 항목이 있을때 최대 n번의 검색을 해야 하므로 상한이 O(n)이 되지만 운이 좋다면 한 번만에 검색을 끝낼수도 있으므로 하한은 Ω(1)이 된다.
Big O 표기와 동일하게 아래 목록과 같은 Big Ω 표기가 많이 사용된다.
- Ω(n^2)
- Ω(n log n)
- Ω(n)
- Ω(log n)
- Ω(1)
생각해보기
실행시간의 상한이 낮은 알고리즘이 더 좋을까요, 하한이 낮은 알고리즘이 더 좋을까요?
데이터가 커지면 커질수록 Big O의 각 단계 별 실행 시간은 엄청난 차이가 생긴다.
따라서 보편적으로 실행시간의 상한이 낮은 알고리즘이 더 좋다고 말할 수 있다.
