[algorithm] 빅오 표기법과 시간제한

시간 복잡도

알고리즘의 수행 시간을 표기하는 방법 여러가지가 있지만 빅오표기법을 많이 쓴다. 시간 제한 안에 내 코드가 실행되는지 확인할 수 있는 쉬운 방법이다.

빅오 표기법

함수의 상한을 나타낸다. N에 대한 함수 $f(N)$이 있을 때

$f(N) = O(g(N))$ 의 의미는

O 표기를 구하는 방법

반복문이 몇 번 실행되는가를 구하면 된다.

수행시간 어림짐작해보기

1초당 수행횟수 1억번을 넘으면 시간제한 초과 가능성이 있다.

먼저 내가 작성한 코드를 빅오 표기법으로 표현한다. 가령 중첩 for문일 경우 $n^2$이 될텐데, 최대 케이스를 대입하여 나온 횟수가 1억번 이내일 경우 보통 들어맞는다고 한다.

케이스가 1만번일 경우 제곱을 했을 때 1억번이 나오므로 채점을 해볼만 하다. 하지만 빅오 표기법은 알고리즘의 최악의 수행시간과 관련이 없다 입력 크기와 시간 복잡도 외의 요소들이 수행시간에 미치는 영향이 꽤 크기 때문에 여유를 두는 것이 좋다.

끝