[Coding Test] 시간 복잡도 총정리!

 

입력의 최대 크기와 알고리즘의 시간 복잡도를 보고

수행 시간을 어림짐작할 수 있어야 한다고 해요!

 

알면서도 매번 코드 구현만 하던 나 자신 반성하며,,

이번 기회에 시간 복잡도에 관련된 내용을

정리하는 포스팅을 해보려고 합니다 ! 

 

 

알고리즘 시간복잡도는 주로 빅오 표기법을 사용해서 표기합니다.

O < (1) < O(logn) < O(N) < O(nlogn) < O(n^2) <  O(n^3) <O(2^n)

 

 

참고로 빅오 표기법에서 상수는 버립니다.

예를 들어 O(3N)은 O(N)으로 표기합니다.

 

---

입력된 수 = N,

시간 제한이 1초라고 가정한다.

 

N의 범위가 500이라면? 

: 시간 복잡도가 O(n^3)인 알고리즘까지 설계가 가능하다.

 

N의 범위가 2,000인 경우

: 시간 복잡도가 O(n^2)인 알고리즘까지 설계가 가능하다.

 

N의 범위가 100,000인 경우 (10만)

: 시간 복잡도가 O(nlogn)인 알고리즘까지 설계가 가능하다.

 

N의 범위가 10,000,000인 경우 (1000만)

: 시간 복잡도가 O(N)인 알고리즘까지 설계가 가능하다.

---

참고하면 좋을만한 포스팅 링크

 

https://book.algospot.com/estimation.html

알고리즘 문제 해결 전략