-1

我现在一直在研究一个问题集，我似乎已经掌握了用于重复示例的主方法。但是，我发现自己在使用其他方法（递归树、替换）时遇到了困难。这是我坚持的问题： T(n) = T(n-2) + n^2 是否有如下模式？n^2 + T(n-2) + T(n-4) +... 直到没有剩下的 n 为止。所以大约 n/2 次，这是否意味着 n^2 + (n-2)^2 + (ni) ^2 所以渐近界将是 theta(n^2)？

老实说，我在这里在黑暗中拍摄，所以我希望有人可以帮助指导我如何解决这些问题。也许不是对这个问题的直接回答，但最好是暗示我应该从哪里开始。

4

2 回答 2

2

正如你所说，结果将是 n^2 + (n-2)^2 + (n-4)^2 + ...

直觉上你可以感觉到，因为总和中有很多 (n/2) 个元素，所以它会超过 O(n^2) - 与 1 + 2 + 3 + ... + n 相同的方式更多比 O(n)。

证明它的一种方法是，您可以用所有平方数之和的一半来近似总和，对此有一个公式。所以它是 Theta(n^3)。

于 2013-02-05T09:47:27.650 回答
1

以下是如何将总和按摩到结果中

n^2 + (n-2)^2 + ... + (n -2i) + ...

= {just writing in a different way}

(2n/2) + (2n/2 - 2)^2 + ... + (2n/2 -2i)^2 + ...

= {write m = n/2}

(2m)^2 + (2m-2)^2 + ... (2m - 2i)^2 + ...

= 4 ( m^2 + (m-1)^2 + ... (m-i)^2 ...)

= 4 ( sum (k^2) from k=1 to m)

= 4 ( sum (k^2) from k=1 to n/2)

= (n^3 + 3n^2 + 2n)/6

使用公式

于 2013-02-05T10:10:53.030 回答