Loading [MathJax]/jax/output/CommonHTML/jax.js

읽기 전

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

시간 복잡도 예제

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

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

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

logn!=nlognn+O(logn)

적당히 log를 자연로그라고 생각하고 전개하면 lnn!=ln1++lnn이며 n의 값이 커지면 적분 값과 유사므로 n1lnx dx로 표현할 수 있다. 적분 공식을 전개하면 nlnnn이다. 뒤의 O(logn)은 근사 과정에서 발생하는 오차를 보정하기 위함이다.

사실 좀 더 엄밀하게 말하면 n!의 근사는 2πn(ne)n이고 양변에 로그를 취하면 log2n!nlog2nnlog2e+12(log2n+log2π)가 되고 시간 복잡도 관섬에서 계수를 모두 소거하면 nlnnn+O(logn)이 되는 것이다.

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

참고자료

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


+ Recent posts