시간복잡도 - 빅오 표기법

빅오 표기법은 다음과 같이 나타낸다.

시간에 따라서 나열해보면 나타낼 수 있다.

O(2^n) > O(n^2) > O(n log n) > O(n) > O(log n) > O(1)

입력 범위 n을 기준으로 로직이 몇 번이나 반복되는지 나타내는 것

가장 영향을 많이 끼치는 항의 상수 인자를 뺀 나머지 항을 없앤것이다.

예를 들어, n(n + 1)/2 의 경우에는 O(n^2)로 나타낼 수 있다.

필요성

효율적인 코드로 개선하는 데 쓰이는 척도가 된다.

예를 들어 O(n^2)의 시간 복잡도를 가지고 16초가 걸리는 경우에
O(n)으로 알고리즘을 개선한다면,

4초로 줄어들게 된다

따라서, O(2^n)에서 O(1)의 방향으로 개선을 지향해야한다.