-1

如果有人可以帮助我解决几个问题，我将不胜感激，

对于以下每个递归函数定义，使用主定理确定其渐近增长顺序（即 Big-Tetha）。如果您认为 Master 定理不适用于某种情况，请正确解释原因。在这些情况下，您还能为运行时间提供一个合理的上限（即 Big-O）吗？请注意，基本情况都假定为常数。

(a) T (n) = T(n/2) + 2^n

(b) T (n) = 4T(n/2) +(n^1.5) - 1

(c) T (n) = T(n/3) + 100

(d) 是 T(n) = 125T(n/5) + n^3/logn

(e) T (n) = 2T(n/7) + log n + √n

我刚刚在网上阅读了一些关于此的内容，但我无法获得足够的理解来回答这个问题。任何帮助将不胜感激，我正在努力学习考试，但我没有得到任何帮助！

非常感谢！

4

1 回答 1

0

除了 (a) 之外的所有项目都适用于 Masther 定理。在情况 (a) 中，toll​​ 函数不是多项式，因此主定理不适用。但是可以通过扩展来解决它：

T(n) = 2^n + T(n/2) 
     = 2^n + 2^(n/2) + T(n/4) 
     = 2^n + 2^(n/2) + 2^(n/4) + T(n/8)
     = ... 
     = O(2^n).

通过将递归解释为二进制数之和，结果很清楚：1+10+100+10000+10000000 <= 2*10000000。

于 2013-10-16T13:28:24.140 回答