我被一个重复出现的问题困住了。
T(n)=T(n/2)+ log N
我现在拥有的是:
T(N) = T(N/2) + log N
T(N/2) = T(N/4) + log(N/2)
...
T(N) = T(N/2^k) + sum[i=0 和 k {log (N/2^i)}]
我不知道下一步该做什么。请给我一些建议。
谢谢!
最佳答案
另一种方法是使用 Master Theorem (或在 Wikipedia 上)。对于大多数重复情况，它都是适用的，并且可以非常快速地提供答案。
它基本上给你三个类别，然后答案就出来了。给定 T (n) = aT (n/b) + f (n) 形式的递推，我们寻找 a、b 和 f(n)。在你的例子中，我们有a=1，b=2，f(n)=log n。
因此(您必须查看引用的链接)我们属于情况 2，其中 f(n) 位于 Theta(n^(log_b(a-eps)) log^k(n)) = Theta(n ^0 log(n))，则主定理指出 T(n) 位于 Theta(n^(log_b(a-eps)) log^(k+1)(n)) = Theta(log^2( n))
关于algorithm - 递归:T(n)=T(n/2)+ log N，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/42406680/