Big O 표기법

Big O 표기법이란?

 

알고리즘의 성능을 수학적으로 표기한 것이다. 

알고리즘의 시간/공간 복잡도 표현할 수 있다. 

실제 러닝 타임보다는, 데이터나 사용자의 증가율에 따른 알고리즘의 성능 예측이 목표다. 그래서 상수를 1로 취급하는 것이다.

 

(1) O(1) 알고리즘 -> 입력 데이터의 크기에 상관없이, 언제나 일정한 시간이 걸림.

데이터가 증가해도 걸리는 시간(성능)은 변하지 않는다.

 

 

(2) O(N): 입력 데이터의 크기에 비례해서 처리 시간 증가 (N이 늘어날 때마다)

 

(3) O(mN)

(4) O(N제곱)

(5)O (N 세제곱) 등이 있음.

 

O(log N) - binary search

한번 검색할 때마다, 검색해야하는 양이 반으로 줄어듬.

데이터가 늘어남에 따라서, O(n)보다 O(log(n))의 처리 시간이 훨씬 적게 든다.

 

Big O 에서 중요한 것 상수는 과감하게 버린다.

Big O 에서는 O(2N은 O(N)) 으로 과감하게 표시한다.

O(N제곱 + N제곱)도, 앞의 상수 무시하고, 그냥 O(N제곱)이라고 표시한다.

 

출처

https://www.youtube.com/watch?v=6Iq5iMCVsXA