시간 복잡도 총정리(입력 수에 따른 시간 복잡도 정하기)

항상 코딩테스트를 칠 때도 그렇지만, 개발할 때 최대한 효율적인 코드를 짜야하고 효율적이라는 것은 빠르게 동작하는 것으로 봐도 무방하다.

나중에 도움이 될 것 같아서 입력 수에 따른 시간 복잡도 설계를 어떻게 둘지 팁을 알아봤다.

입력된 수가 N일 때, 시간 제한이 1초(1억번 연산) 라고 가정.

N의 범위가 500일 때,

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

N의 범위가 2000일 때,

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

N의 범위가 100,000일 때, (10만)

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

N의 범위가 10,000,000일 때, (1000만)

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

참고자료

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