2

我有这个复发：

T(n)= 2T(n/2) + (n-1)

我的尝试如下：

树是这样的：

T(n) = 2T(n/2) + (n-1)
T(n/2) = 2T(n/4) + ((n/2)-1)
T(n/4) = 2T(n/8) + ((n/4)-1) 
...
  • 树的高度：(n/(2 h ))-1 = 1 ⇒ h = lg n - 1 = lg n - lg 2
  • 最后一级的成本：2 h = 2 lg n - lg 2 = (1/2) n
  • 直到级别 h-1 的所有级别的成本：Σ i=0,...,lg(2n) n - (2 i -1)，这是一个几何级数，等于 (1/2)((1/2 )n-1)

所以，T(n) = Θ(n lg n)

我的问题是：对吗？

4

2 回答 2

3

不，不是。你有最后一级的成本是错误的，所以你从中得到的也是错误的。

（我假设你想自己找到复杂性，所以除非你问，否则没有更多的提示。）

编辑：根据要求提供一些提示

为了找到复杂性，一个通常有用的方法是递归地应用方程并将结果插入第一个，

T(n) = 2*T(n/2) + (n-1)
     = 2*(2*T(n/4) + (n/2-1)) + (n-1)
     = 4*T(n/4) + (n-2) + (n-1)
     = 4*T(n/4) + 2*n - 3
     = 4*(2*T(n/8) + (n/4-1)) + 2*n - 3
     = ...

这通常会导致一个封闭的公式，您可以通过归纳证明（如果您有足够的经验，则无需执行证明，然后您无需写下证明即可看到正确性）。

剧透：您可以在几乎任何处理Master Theorem的资源中查找复杂性。

于 2011-11-29T19:35:57.943 回答
0

这可以通过Masters theorem轻松解决。

你有a=2, b=2,f(n) = n - 1 = O(n)因此c = log2(2) = 1. 这属于马斯特定理的第一种情况，这意味着复杂度是O(n^c) = O(n)

于 2015-12-14T00:26:30.853 回答