algorithm - 主定理和指数函数

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