主定理和指數函數

Question

我最近遇到了關於主定理和排序的一些練習。一個要求我們找到某些表達式的Θ（）（給定T（1）=Θ（1））。 大多數人與主定理解決了，但是這一次

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

顯然不解決這樣的，因爲它不是定理的一般形式。
我們如何找到它的Θ（）？

Answer 1

您可以對該系列進行望遠鏡相對容易地找到解決方案。無論在遞歸關係中的權力（假設它小於一），它就是Theta(log n)。這裏用c而不是5/6。

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) >= log n，所以T(n) = Theta(log n)。