3

需要一点帮助！这是我到目前为止使用向后替换的内容：

T(n) = 2T(n/2) + sqrt(n), where T(1) = 1, and n = 2^k
T(n) = 2[2T(n/4) + sqrt(n/2)] + sqrt(n) = 2^2T(n/4) + 2sqrt(n/2) + sqrt(n)
T(n) = 2^2[2T(n/8) + sqrt(n/4)] + 2sqrt(n/2) + sqrt(n)
     = 2^3T(n/8) + 2^2sqrt(n/4) + 2sqrt(n/2) + sqrt(n)

一般来说

T(n) = 2^kT(1) + 2^(k-1) x sqrt(2^1) + 2^(k-2) x sqrt(2^2) + ... + 2^1 x sqrt(2^(k-1)) + sqrt(2^k)

到目前为止这是正确的吗？如果是，我不知道如何简化它并将其简化为一个通用公式。

我猜是这样的？结合条款

= 1 + 2^(k-(1/2)) + 2^(k-(2/2)) + 2^(k-(3/2)) + ... + 2^((k-1)/2) + 2^(k/2)

这就是我卡住的地方。也许是一种分解 2^k 的方法？任何帮助都会很棒，谢谢！

4

2 回答 2

3

你已经成功了一半。表达式可以简化为：

于 2013-04-28T05:25:08.207 回答
2

如果您只想要一个大 O 解决方案，那么Master Theorem就可以了。

如果你想要一个精确的方程，递归树很好。像这样：

在此处输入图像描述

右边是每个级别的成本，很容易找到成本的一般形式，即sqrt((2^h) * n). 然后，总结您可以获得 T(n) 的成本。

  1. 根据 Master Theorem，是情况 1，所以O(n).
  2. 根据递归树，确切的形式应该是sqrt(n)*(sqrt(2n)-1)*(sqrt(2)+1)，它对应于大 O 符号。

编辑：

递归树只是所谓的backward substitution. 如果你总结右手边，即cost，你可以得到 的广义形式T(n)。所有这些方法都可以在introduction to algorithm

于 2013-04-28T04:36:05.027 回答