计算 2 次递归调用的大 Theta 边界

Question

T(m,n) = 2T(m/2,n)+n，如果 m<2 或 n<2，则假设 T(m,n) 是常量所以我不明白的是，这个问题可以用Master Theorem解决吗？如果是这样怎么办？如果不是，这 table 正确吗？

level   # of instances  size    cost of each level  total cost
0              1        m, n            n                n
1              2       m/2, n           n               2n
2              4       m/4, n           n               4n
i             2^i    m/(2^i), n         n             2^i * n
k              m        1, n            n               n*m

谢谢！

Answer 1

Master Theorem 在这里可能有点矫枉过正，您的解决方法也不错（log 表示以 2、c=T(1,n) 为底的对数）：

T(m,n)=n+2T(m/2,n)=n+2n+4T(m/4,n)=n*(1+2+4+..+2^log(m))+2^log(m)*c
      =n*(2^(log(m)+1)-1)+m*c=Theta(n*m)

如果您通过将 n 视为常数来使用主定理，那么根据 n，您将很容易获得具有常数 C 的 T(m,n)=Theta(m*C(n))，但是Master Theorem 并没有告诉你很多关于这个常数 C 的信息。如果你太聪明和不专心，你很容易被烧伤：

T(m,n)=n+2T(m/2,n)=n*(1+2/nT(m/2,n))=n*Theta(2^(log(m/n)))
      =n*Theta(m/n)=Theta(m)

而现在，因为您在第三步中遗漏了 C(n)，所以您得到了错误的结果！

计算 2 次递归调用的大 Theta 边界

Calculate big Theta bound for 2 recursive calls

algorithm

recurrence

big-theta