알고리즘 표기법
-
[알고리즘] 알고리즘 표기법Stage/Computer Science 2021. 5. 29. 00:44
학습 목표 알고리즘 실행 시간의 상한과 하한을 표기할 수 있다. 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..