안녕하세요
T(n) = T(n-1) + 2log(n), T(0)=0 을 풀려고 합니다.
T(n) = T(n-1) + 2log(n)
= T(n-2) + 2log(n-1) + 2log(n)
= T(n-3) + 2log(n-2) + 2log(n-1) + 2log(n)
= T(n-4) + 2log(n-3) + 2log(n-2) + 2log(n-1) + 2log(n)
.
.
.
= T(0) + 2log(n) + 2log(n-1) + ... + 2log(3) + 2log(2) 이렇게 되어버립니다.
그러면 답은 2log(n) + 2log(n-1) + ... + 2log(3) + 2log(2) 이 되는 건가요?
2log(n!)
n!은 스탈링 정리에 의해서 근사값을 구할 수 있음. n!은 n이 졸라 크면 sqrt(2*PI*n)*(n/e)^n 으로 근사할 수 있음
2로 log를 취하면 log(sqrt(2*PI)) + log(sqrt(n)) + nlog(n/e)니까 결국 O(nlogn)혹은 Theta(nlogn)이 됨
감사합니다! 이거는 수학적 지식이 필요한건가요?