민팽로그

시간복잡도와 수행시간 본문

PS

시간복잡도와 수행시간

민팽 2021. 12. 2. 03:08

대략 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초 제한이라고 하면 어느정도?)

우리가 흔히 Big O notation을 많이 사용한다. 예를 들어 이중 for 문을 사용하면 시간 복잡도는 흔히 O(N^2) 이라고 하고, 단순 for 문을 사용하면 시간 복잡도는 흔히 O(N)이라고 한다. 그런데 알고리즘

lemonlemon.tistory.com

 

'PS' 카테고리의 다른 글

정수에 콤마(,) 찍기  (0) 2021.12.01
Comments