Analysis of Algorithms | A Time Complexity Question

읽기 전

• 해당 게시물은 작성자가 학습한 내용을 정리 및 요약 목적으로 작성되었으므로 오역 및 오개념이 있을 수 있습니다. 바로잡기 위한 의견을 제시해주시면 매우 감사하겠습니다.

시간 복잡도 예제

void fun(){
  int i, j;
  for (i=1; i<=n; i++)
      for (j=1; j<=log(i); j++)
          printf("check!")
}

위 함수의 경과 시간을 1항부터 나열하면 $\theta(\log{1})+\theta(\log{2})+\cdots+\theta(\log{n})$이 되어 전체 경과 시간은 $\theta(\log{n!})$이 됨을 알 수 있다. 그리고 $\log{n!}$의 $n$값이 발산하면 증가폭은 $n\log{n}$과 동일하므로 위 함수의 시간복잡도는 $\theta{n\log{n}}$으로 표현할 수 있다. $\theta(\log{n!})$이 $\theta (n\log{n})$과 동일 증가폭을 갖는다는 개념은 Stirling's Approximation에서 확인할 수 있다.

스털링 근사(Stirling's Approximation, Stirling's fomula)

$\log{n!} = n\log{n} - n + O(\log{n})$

적당히 log를 자연로그라고 생각하고 전개하면 $\ln{n!}=\ln{1}+\cdots+\ln{n}$이며 $n$의 값이 커지면 적분 값과 유사므로 $\int_{1}^{n} \ln{x}\ dx$로 표현할 수 있다. 적분 공식을 전개하면 $n\ln{n}-n$이다. 뒤의 $O(\log{n})$은 근사 과정에서 발생하는 오차를 보정하기 위함이다.

사실 좀 더 엄밀하게 말하면 $n!$의 근사는 $\sqrt{2\pi n}(\cfrac{n}{e})^n$이고 양변에 로그를 취하면 $\log_2{n!}\approx n\log_{2}{n}-n\log_{2}{e}+\cfrac{1}{2}(\log_{2}{n}+\log_{2}{\pi})$가 되고 시간 복잡도 관섬에서 계수를 모두 소거하면 $n\ln{n}-n+O(\log{n})$이 되는 것이다.

정확한 유도 및 증명과정은 위키피디아에 있으므로 포스팅에서 자세히 다루지 않는다.

참고자료

1. A Time Complexity Question
2. Stirling's approximation