읽기 전
- 해당 게시물은 작성자가 학습한 내용을 정리 및 요약 목적으로 작성되었으므로 오역 및 오개념이 있을 수 있습니다. 바로잡기 위한 의견을 제시해주시면 매우 감사하겠습니다.
시간 복잡도 예제
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!=nlogn−n+O(logn)
적당히 log를 자연로그라고 생각하고 전개하면 lnn!=ln1+⋯+lnn이며 n의 값이 커지면 적분 값과 유사므로 ∫n1lnx dx로 표현할 수 있다. 적분 공식을 전개하면 nlnn−n이다. 뒤의 O(logn)은 근사 과정에서 발생하는 오차를 보정하기 위함이다.
사실 좀 더 엄밀하게 말하면 n!의 근사는 √2πn(ne)n이고 양변에 로그를 취하면 log2n!≈nlog2n−nlog2e+12(log2n+log2π)가 되고 시간 복잡도 관섬에서 계수를 모두 소거하면 nlnn−n+O(logn)이 되는 것이다.
정확한 유도 및 증명과정은 위키피디아에 있으므로 포스팅에서 자세히 다루지 않는다.
참고자료
'Algorithms > Geeks for Geeks' 카테고리의 다른 글
Analysis of Algorithms | Time Complexity where loop variable is incremented by 1, 2, 3, 4 .. (0) | 2020.09.17 |
---|---|
Analysis of Algorithms | Time Complexity of building a heap (0) | 2020.09.17 |
Analysis of Algorithms | Polynomial Time Approximation Scheme (0) | 2020.09.14 |
Analysis of Algorithms | NP-Completeness (0) | 2020.05.15 |
Analysis of Algorithms | Pseudo-polynomial Algorithms (0) | 2020.05.15 |