0

我最近遇到了一些关于主定理之类的练习。一个要求我们找到一些表达式的 Θ()(给定 Τ(1)=Θ(1))。大多数都用主定理解决了,但是这个

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

显然不是这样解决的,因为它不是定理的通用形式。
我们如何找到它的 Θ()?

4

1 回答 1

1

您可以伸缩该系列以相对容易地找到解决方案。递归关系中的Theta(log n)幂无关紧要(假设它小于一)。这里用c5/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)

于 2017-04-19T01:20:10.463 回答