主定理和指数函数

Question

我最近遇到了一些关于主定理之类的练习。有人要求我们找到某些表达式的 Θ()（给定 Τ(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)。

Master Theorem and exponential functions