Big-O 표기법

시간복잡도 순서 : O(1) -> O(log n) -> O(n) -> O(nlogn) -> O(n^2)

​

1. O(1)

print와 단순 변수 대입의 경우에 O(1)의 복잡도를 가진다.

​

단, 특수 케이스로 for문이 if문으로 감싸고 있다면 그건 O(n)이 아닌 O(1)로 취급한다.

why? 조건에 따른 변수 대입으로 가정하기 때문이다.

​

2. O(logn)

예를 들어 2의 제곱을 계속 진행했을 경우 n의 값에 도달한다면 log2n, 제곱수로 목표에 도달하기 때문에 O(n)보다 훨씬 빠르다 .

​

3. O(n)

for문이 하나가 있을 경우에 O(n)의 복잡도를 가진다.

​

4. O(nlogn)

logn을 n번만큼 하는 복잡도, O(n^2)대신 O(nlogn)을 만들 수 있다면 엄청난 성능향상을 기대할 수 있다.

​

5. O(n^2)

2승의 경우 이중 for문을 이야기한다. 결론적으로 다중for문으로 갈 경우 최악의 성능이 나온다.

되도록이면 이 복잡도를 쓸 때 코드를 많이 신경쓰면서 코딩을 해야한다.

​