假设我有一个像 T(n)=2T(n/4)+1 这样的情况。f(n)=1 a=2 和 b=4。因此n^(1/2)>1。那应该是第一种情况。但是在第一种情况下也有一个 lambda，因此对于某些 lambda >0，f(n)=O(n^((1/2)-lambda))。在这种情况下，lambda 将是 1/2？
问问题
1627 次
1 回答
2
对，那是正确的。请注意，在这种情况下，我们有 a = 2 和 b = 4。在这种情况下，函数 f(n) 是 1，对于某些 ε > ，我们确实有 1 = Θ(n 1/2 - ε ) 0，在这种情况下 ε = 1/2。因此，根据主定理，您将得到 T(n) = Θ(n 1/2 )。
这个 ε 的要点是，如果每个级别完成的工作量足够小（低于 log b a），那么工作主要由拆分而不是每个级别的工作占主导地位。您可以从指数中减去 ε > 0 的事实表明，每级的功必须严格渐近地增长慢于分裂率，并且必须以某个多项式量增长。
希望这可以帮助！
于 2012-02-01T05:53:30.450 回答