解决递归 T(n) = 2T(n/2) + sqrt(n)。

Question

需要一点帮助！这是我使用反向替换得到的结果：

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次方吗？ 任何帮助都将不胜感激，谢谢！

- Nunes

---

如果你正在寻找一个大O解决方案，主定理可以做到这一点。 - gongzhitaao

在每次迭代中，将n替换为2^k，您将首先得到2^(k-1)，然后是2^(k-2)，最终是2^0。您需要进行k次调用，其中k等于log2(n)... 因此T(n)的复杂度为O(log(n))。 - Déjà vu

Answer 1

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

- SomeWittyUsername

---

啊哈，所以n + n/sqrt(2) + n/sqrt(4) + .. + 1 = sqrt(n)(sqrt(2n)-1)(sqrt(2)+1)？你知道是否有一般的求和公式用于生成它吗？ - Nunes

@user1201359 寻找等比数列的和。 - SomeWittyUsername

好的，我会尝试推导出通用公式，谢谢！ - Nunes

Answer 2

如果您只需要一个大O解决方案，那么主定理就足够了。

如果您需要一个准确的方程式，递归树是个不错的选择。例如：

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

1. 根据主定理，这是第一种情况，因此为O(n)。
2. 根据递归树，精确形式应该是sqrt(n)*(sqrt(2n)-1)*(sqrt(2)+1)，它与大O符号相对应。

编辑：

递归树只是所谓的“反向代换”的可视化形式。如果您总结右手边，即cost，则可以得到T(n)的一般形式。所有这些方法都可以在《算法导论》中找到。

- gongzhitaao

---

这不应该是O(log(n))吗？ - Déjà vu

我确实需要一个精确的公式，但老师希望使用反向替换的方式来解决它。我认为我走在了正确的轨道上，只需要弄清楚如何因式分解和简化它。 - Nunes

@ring0 为什么是O(log(n))？根据主定理，这满足情况1，所以应该是O(n)。 - gongzhitaao

@user1201359 抱歉，缺少一个因素。请查看更新后的内容。 - gongzhitaao

@icepack 对于我之前的回答，非常抱歉。下次我会更加小心。但是替换和递归树实际上是同一件事，就像我之前说的，递归树只是替换的可视化表示。 - gongzhitaao