algorithm - 递归关系。请告诉我哪里出错了

Question

在我的作业问题中，我被要求解决以下递归关系，T(n) = T(√n) + T(n - √n) + cn

这就是我解决相同问题并得到正确答案的方法。但是我的解决中有一个明显的错误。请指出如何纠正我的错误步骤。

对于所有 n > 4，我们有 , √n < (n-√n)

因此，项 T(n - √n) 将缓慢地向 T(1) 移动，从而有助于递归树的高度。

通过简单的数学，我们可以说在 √n 次迭​​代之后，项 T(n - √n) 最终将是 T(1)。（这是我出错的地方。我原以为这些术语会减少如下， T(n - √n) ， T(n - 2√n) ， T(n - 3√n) 但他们没有）

因此上述树的高度为√n。

此外，每个级别的运营成本最多为 cn。

因此，操作的总成本为 √n * cn。

因此算法的运行时间为 O(n√n)

Answer 1

您的总体想法是正确的，正如您提到的，树的高度最多为 √n，但您的答案中的错误部分是：“每个级别的操作成本也最多为 cn”。

树的宽度在每个级别增长两倍，直到深度 log log n，（意味着到某个点，树的宽度增长非常快），并且在特定行中的每个顶点中，您必须执行 O(n)操作，这意味着在每一行中，您的操作都比 cn 多（平均而言）。

如果要处理这个问题也不错考虑以下情况：

n=2 ^{2 s}，并查看您的函数的行为。