[코딩 테스트-참고] 시간 복잡도별 연산량

알고리즘 문제를 풀이할 때, 제한 조건에 시간 제한이라는 것이 존재한다.
작성한 알고리즘이 의도한 결과를 잘 만들어 낼 수 있다고 해도 제한 시간 안에 결과를 내지 못하면 안된다는 것이다. 그러기 때문에 우리는 알고리즘을 작성하기 전에 내가 작성할 알고리즘의 시간 복잡도를 계산하여 제한 시간 안에 결과를 만들어 낼 수 있는지 검증해야 한다.
이를 위해서는 내가 사용할 라이브러리나 알고리즘의 시간 복잡도를 알고 있어야 한다. 그러면 이들을 종합한 시간 복잡도를 확인하여 내가 작성할 알고리즘이 제한 시간 범위 안에 있다는 것을 검증할 수 있게 된다.

시간 복잡도별 가능한 연산 횟수

• O(N) : 약 1억
• O(NlogN) : 약 1000만
• O(N^2) : 약 10만
• O(N^3) : 약 500
• O(2^N) : 약 20
• O(N!) : 약 10

O(1) < O(logN) < O(N) < O(NlogN) < O(N^2) < O(2^N) < O(N!) < O(N^N)

출처

• Big O notation 과 시간 제한
• 코딩 테스트 문제 풀 때, 시간 복잡도 계산해보기