algorithm - t(n)的运行时间= t(n-2)+(n-2)²

Closed. This question is off-topic. It is not currently accepting answers. Learn more。
想改进这个问题吗？Update the question所以堆栈溢出的值小于aa>。
有人能告诉我下面的解决方案是否正确吗？
我试图计算t（n）=t（n-2）+（n-2）的运行时间
进一步评估
=>t（n）=t（n-4）+（n-2）平方+n平方
=>t（n）=t（n-6）+（n-6）平方+（n-2）平方+n平方
…因为它减少了2，所以它有大约n/2个项，并且通过扩展所有的平方
我们有（n/2）*（n m2）等于n m3，所以运行时间是θ（n m3）
这是正确的解决方案吗？

最佳答案

是的，以上是完全正确的（根据问题定义，第一行的小例外应该t(n) = t(n-4) + (n-4)^2 + (n-2)^2，并纠正接下来的内容-但它不影响渐近结果）。
为了证明这一点，我们可以使用mathematical induction：

Claim: t(n) <= n^3
base: T(2) = 2 (assumption - otherwise we'll get stuck)
let's assume the assumption is true for each n<k for a certain k.
t(k) = t(k-2) + (k-2)^2 <= (k-2)^3 + (k-2)^2 =
     = k^3 -6k^2 + 12k -8 + k^2 - 4k + 4
     = k^3 -5k^2 + 8k - 4

剩下的就是证明5k^2 >= 8k - 4我们已经完成了这个公式适用于每个k>=2-证明它是作为一个exrecise保留的。
从上面我们可以得出t（n）在O(n^3)中。使用类似的方法，我们可以显示它也在Omega(n^3)中，因此它是Theta(n^3)

关于algorithm - t(n)的运行时间= t(n-2)+(n-2)²，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/12541743/