마스터 정리 및 지수 함수

Question

최근 마스터 정리 및 정렬에 관한 몇 가지 연습 문제가있었습니다. 일부 표현식의 Θ()를 찾도록 지시했습니다 (Τ (1) = Θ (1)). 대부분은 마스터 정리와 해결되었지만,이 이론의 일반적인 양식을하지 않습니다 이후이 하나

T(n)=T(n^(5/6))+Θ(logn) 

분명히, 그렇게 해결되지 않습니다.
어떻게 Θ()를 구합니까?

Answer 1

비교적 쉽게 솔루션을 찾을 수 있도록 시리즈를 망원경으로 연결할 수 있습니다. 반복 관계의 힘에 상관없이 Theta(log n)입니다 (1보다 작다고 가정). 여기에 5/6 대신에 c이 있습니다. 사소 T(n) >= log n

T(n) = T(n^c) + log n 
    = log n + log(n^c) + log(n^(c^2)) + log(n^(c^3)) + ... 
    = (1 + c + c^2 + ...)(log n) 
    <= (log n)/(1 - c) 

, 그래서 T(n) = Theta(log n).