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

우리가 흔히 Big O notation을 많이 사용한다.

예를 들어 이중 for 문을 사용하면 시간 복잡도는 흔히 O(N^2) 이라고 하고, 단순 for 문을 사용하면 시간 복잡도는 흔히 O(N)이라고 한다. 그런데 알고리즘 문제들을 풀어보면 시간제한 1초 이런식으로 시간제한이 있는 경우가 많다.

그렇다는 말은 미리 문제를 풀기 전에 이 문제를 제한 시간 안에 끝낼 수 있을지 없을지를 알아야 한다는 것인데 Big O notation으로 시간복잡도를 구하더라도 이것을 초로 바꾸지 못한다면 아무 의미가 없다.

따라서 오늘은 보통 1초 제한이라고 하면 빅 오로 얼마 정도가 나와야 하는지에 대해서 알아보겠다.

결론부터 말하면 n으로 구성된 O( )를 계산했을 때의 값이 1억 정도면 1초 정도의 시간이 걸린다고 한다.

물론 이 값은 정확한 것이 아니고 문제와 알고리즘에 따라서 달라질 수 있는 것이지만 보통 자신의 알고리즘이 몇 초안에 끝날지를 계산하기 위해서는 1억 정도의 값이 1초라는 것을 알면 계산이 쉬워진다.

예를 들어 N의 최대값이 10만이라고 문제에서 주어진다면

1. O(N) 의 시간복잡도일 경우에 값이 10만 정도이니, 1/1000초 정도가 걸릴 것이라고 예상할 수 있다.

2. O(N^2)의 시간복잡도의 경우에 값은 100억이므로, 100초 정도가 걸릴 것이라고 예상할 수 있다.

이처럼 만약 문제 제한이 1초라면 O(N^2)의 시간복잡도를 가지는 알고리즘으로 문제를 풀면 안되겠다라는 생각을 할 수 있다.

1억정도면 1초가 걸린다는 것은 대략적인 추정치이고 실제는 이와 다를 수 있다

보통 1초가 걸릴 때 입력의 최대 크기를 살펴보면

이라고 한다. 시간복잡도가 커질수록 입력의 최대 크기는 매우 작아지고,

이는 다시 말해서 만약 입력의 크기가 크지 않다면 O(N!) 과 같은 알고리즘을 사용해도 시간제한 안에 문제를 해결할 수도 있다는 말이다.

문제에서 시간제한과 자신이 사용할 알고리즘을 미리 잘 구상하여 시간제한을 초과하는 경우를 방지하자.