점근선 상한선과 하한선 찾기?

Question

T (n)이 작은 n에 대해 일정하다고 가정하면이 함수의 해를 어떻게 찾을 수 있습니까?

T(n) = T(n−2) + 2logn 

지금까지는 전체 기능을 나타내는 방법을 찾을 수 없습니다. 저를 도와주세요? 나는 정말로 이해하고 싶다.

Answer 1

n이 짝수라고 가정하면, T(1) = T(0) = 0입니다. n도, T(n) = Theta(n log(n))에 대한 그래서

T(n)/2 = log(n) + log(n-2) + ... + log(2) 
     = log((n/2)! * 2^n) 
     = n log(2) + log((n/2)!) 
     = n log(2) + n log(n) - n + O(log(n)) (Stirling's approximation) 

.

n 홀수의 경우, T(n-1) < T(n) < T(n+1)임을 알아 차리고 동일한 점근 적 바인딩을 얻을 수 있습니다.