主定理和指数函数

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)。