-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 回答