시간 복잡도의 계산

속도 순서(밑으로 갈수록 느립니다.)

O(1)

O(log n)

O(n)

O(n log n)

O(n^2)

O(n^3)

O(2^n)

O(n!)

 

입력 개수 100

O(1) = 1

O(log n) = 2

O(n) = 100

O(n log n) = 200

O(n^2) = 10,000(1만)

O(n^3) = 1,000,000(100만)

O(2^n) = 1,267,650,600,228,229,401,496,703,205,376 (1.2676506e+30)

O(n!) = ;;;;;;;;;;;;;;;;;;;

 

벌써부터 어마어마한 숫자가 나옵니다.

 

입력 개수 10만

O(1) = 1

O(log n) = 5

O(n) = 100,000(10만)

O(n log n) = 500,000(50만)

O(n^2) = 10,000,000,000(100억)

O(n^3) = 1,000,000,000,000,000(1000조)

O(2^n) = ;;;;

O(n!) =;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

 

밑의 두 값은 계산이 안됩니다. 컴퓨터 터져요.

알고리즘을 풀다 보면 접하는 시간 복잡도의 예제였습니다.

log n의 값을 착각해 쉬운 문제를 포기했던 제가 너무 멍청해서 올립니다.

 

지수와 팩토리얼은 피합시다.