[CS50] 알고리즘 - 알고리즘 표기법

배정규·2021년 1월 31일
1

알고리즘 표기법

학습 목표

  • 알고리즘의 실행 시간의 상한과 하한을 표기할 수 있다.

핵심 단어

  • Big O
  • Big Ω

Big O

아래 그림과 같이 알고리즘을 실행하는데 걸리는 시간을 표현할 수 있다.
이것을 공식으로 표기한 것이 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 Ω

Big O가 알고리즘 실행 시간의 상한을 나타낸 것이라면, 반대로 Big Ω는 알고리즘 실행 시간의 하한을 나타낸다.
예를 들어 선형 검색에서 n개의 항목이 있을때 최대 n번의 검색을 해야 하므로 상한이 O(n)이 되지만 운이 좋다면 한 번의 검색만으로 끝낼 수 있으므로 하한은 Ω(1)이 된다.
역시 아래 목록과 같은 Big Ω 표기가 많이 사용된다.

  • Ω(n^2)
  • Ω(n log n)
  • Ω(n) - 배열 안에 존재하는 값의 개수 세기
  • Ω(log n)
  • Ω(1) - 선형 검색, 이진 검색
profile
Seize the day

0개의 댓글