[자료구조] 빅오(Big-O)표기법 / 시간복잡도

Big-O

 

알고리즘의 실제 러닝타임보다 데이터나 사용자의 증가율에 따른 알고리즘의 성능을 예측하는 것이 목표이다.

예를 들면 데이터가 무한대로 커졌을 때를 상상해보자. 1+1+1+1....+1 은 2*2*2*2*2......*2에 비하면 아주 미비하게 작아 보일 것이다.

전자의 경우 무한대로 가면 x좌표와 맞닿아있다고 생각할 수도 있다. { O(N+N) => O(N) , O(N^2+N^2) => O(N^2)}

이것을 바탕으로 Big-O표기법을 보면 조금 더 이해가 쉬워진다.

 

•  O(1)

•  O(N)

•  O(N^2)

 

•  O(NM)

 

•  O(N^3)

•  O(2^N)   Fibonacci Numbers

•  O(logN)     Binary Search