PS (Problem Solving)

✅ PS (Problem Solving)

주어진 문제에 대해 제한된 시간과 메모리 내에서 문제를 해결하는 행위를 일컫는 말

  CPU 의 1초간 연산 속도  

Cpu 는 1 초간 약 1 억의 수를 연산할 수 있다고 가정하고 문제를 접근하는 것이 좋다.
입력 N에 대해서 시간 복잡도가 O(n) 이라면 입력 N은 0 <= N <= 100,000,000 까지 연산이 가능하다고 생각하면 된다.

  시간 복잡도 정리  

> O(1) < O(log N) < O(n) < O(N log N) < O(N^2) < O(N^3) < O(2^N) < O(N!)

  1초에 연산 가능한 입력 값 

 O(log N), O(n) 인 알고리즘 :  대략 100,000,000 (1억)
 O(N log N) 인 알고리즘 : 대략 1,000,000 (1백만)
 O(N^2) 인 알고리즘 : 대략 10,000 (1만)
 O(N^3) 인 알고리즘 : 대략 500
 O(2^N)과 O(N!) 인 알고리즘 : 대략 20