[코딩테스트] Big O의 이해

빅 오(Big O)란

 

빅 오(Big O) 란 알고리즘의 복잡도를 나타내는 수학적 방법이다. 

일반적으로 지향되는 알고리즘의 복잡도는 O(1), O(logn) < O(n), O(nlogn) <<< O(n^2), O(2^n), O(n!) 순이다.

 

Big O 표기법은 n이 매우 크다는 것을 가정하므로 상수값에 대한 연산(곱셈, 덧셈 등)을 무시한다. 또한, O() 안에 들어가는 식 중 가장 고차원의 항 미만은 무시된다. 예를 들어, O(n!+n) 의 경우 n의 차원이 n! 보다 작기 때문에 무시되며, O(n!) 과 같다.  

 

Python에서는 일반적으로 list << dictionary, set 순으로 시간 효율성이 좋아지므로 가급적 dict, set 을 이용하는 것을 고려한다.