시간복잡도와 수행시간

대략 1억번 연산에 1초라고 생각하면 된다. 즉 O(N)일 때, N이 100,000,000정도의 크기를 갖는다면 1초가 걸린다.

내가 풀었던 문제에서 내 풀이의 시간복잡도는 O(2^N)이었고, N은 0<= N<= 40이었으며, 제한시간은 0.25초였다. 입력이 30 이상만 되어도 1억이 훌쩍 넘기 때문에 내 풀이로는 0.25초 안에 풀 수 없다. 이처럼 시간제한 내에 문제를 풀기 위해서는 시간복잡도를 함께 생각하며 알고리즘을 선택해야 한다.

아래 블로그 참고!

https://lemonlemon.tistory.com/54

Big O notation 과 시간 제한 (보통 1초 제한이라고 하면 어느정도?)