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

학습 목표

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

1. Big O 표기법

알고리즘을 실행하는 데 걸리는 시간은 아래 그림과 같다.

이 그림을 공식으로 표기한 것이 Big O 표기법이다.

• O 는 "on the order of"의 약자이고, 쉽게 생각하면 "~만큼의 정도로 커지는" 것이라고 볼 수 있다.
• O(n)은 n만큼 커지는 것이므로 n이 커지면 선형적으로 증가한다.
• O(n/2)도 결국 n이 매우 커지면 1/2은 큰 의미가 없어지므로 O(n)이라고 볼 수 있다.
  • 예를 들어, 우리가 푸는 문제가 계속 커져서 저 선들을 더 큰 화면에 담기도록 축소해서 보기 위해 x축과 y축을 늘려보자. 노란 선과 빨간 선은 아주 가까워질 것이고, 계속 축소하다보면 두 선은 결국 거의 같아 보일 것이다.
    
    
    

1.1. 해당 알고리즘

• O(n^2)
• O(n log n)
• O(n) - 선형 검색
• O(log n) - 이진 검색
• O(1)

 

2. Big Ω

Big O가 알고리즘 실행 시간의 상한을 나타낸 것이라면 Big Ω는 알고리즘 실행 시간의 하한을 나타내는 것이다.

2.1. 해당 알고리즘

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