[알고리즘-PS] 1초의 시간동안 CPU가 연산할 수 있는 크기.(알고리즘 문제 풀이에 시간 복잡도 계산하는 방법)

PS를 하다 보면 입력 N에 대한 크기와 시간 복잡도의 관계를 적절하게 잘 파악해야 해당 문제에 어떤 알고리즘이 적합할지를 알 수 있다.

 

오늘은 시간 복잡도의 세세한 내용보다는 실전 PS 파트 이므로 PS에서 시간 복잡도가 어떻게 계산 되는지 정리를 해 보겠다.

 

백준의 문제중 일부

위는 백준의 문제중 일부를 발췌 했는데, 위의 문제 시에 어떤 방식으로 시간 복잡도가 계산 되는지 말 해보겠다.

 

CPU의 1초간 연산 속도

Cpu는 1초간 약 1억의 수를 연산할 수 있다고 가정하고 문제를 접근하는 것이 좋다.

 

그리고 입력 N에 대해서 시간 복잡도가 O(n) 이라면 입력 N은 0 <= N <= 100,000,000 까지 연산이 가능하다고 생각하면 된다.

 

위의 문제로 예를 들었을 때

 

N이 1천 까지로 제한되어 있기 때문에 N을 O(1) ~ O(N!) 까지 계산 해봤을 때 가장 적합한것을 찾으면 된다.

순서는 다음과 같다.

 

• 1. 문제에서 주어진 시간 보기

해당 문제는 3초 이므로

• 2. 문제에서 주어진 입력 N의 크기 보기

해당 문제는 10,000,000

• 3. 문제에서 주어진 시간과 입력 N의 크기 곱하기

해당 문제는 3 * 10,000,000

• 4. 알고리즘 별로 맞는 시간 복잡도 대입히가.

해당 문제는 O(1) ~ O(n) 까지 시간 복잡도가 필요한 알고리즘을 적용할 수 있음.

 

시간 복잡도의 정리

 

1초간 걸리는 입력의 크기 순서.

 

O(1)

O(log N)

O(n)

O(N log N)

O(N^2)

O(N^3)

O(2^N)

O(N!)