빅오(Big-O) 표기

알고리즘 복잡도 공부를 하다보면 다음과 같은 표기를 만날 수 있다.

O(n), O(nlogn), O(n^2)

읽는 방법부터 생소한 표기라 찾는 데 고생을 했다. 먼저, O는 Order의 머리글자로, O(n)의 경우 'n의 오더' 혹은 '오더 n'이라고 읽는다.

빅오 표기란 ?
리미트 n이 무한대로 커졌을 때 최고차항만 고려하는 표기법을 말한다.

예시를 살펴보면,

O(n^2 + 2n + 1)이 있다고 가정했을 때, n이 무한대로 가게 되면 결국 2n과 1은 전체 값에 영향을 미치지 않기 때문에, O(n^2 + 2n +1) = O(n^2)이 될 수 있다.

다음은 시간복잡도를 계산하는 방법에 대해 공부하면 좋을 것 같다