ex) 문제에서 주어진 N의 최대값이 10만이며, 주어진 제한 시간은 1초라면?
시간 복잡도가
O(N^2)
인 알고리즘의 연산 횟수는 10만번*10만번 = 100억번이므로 사용할 수 없다.
시간 복잡도 | 최대 연산 횟수 |
---|---|
O(N) | 약 1억번 |
O(N^2) | 약 1만번 |
O(N^3) | 약 500번 |
O(2^N) | 약 20번 |
O(N!) | 10번 |
O(N^3)
이하인 알고리즘을 설계O(N^2)
이하인 알고리즘을 설계O(NlogN)
이하인 알고리즘을 설계O(N)
이하인 알고리즘을 설계O(logN)
이하인 알고리즘을 설계Reference.