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

Question

有人能告诉我以下解决方案是否正确吗？

我试图计算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平方

...since，它大约有n/2项，通过展开所有的平方(n/2) *(n平方)，等于n³.So，运行时间是θ(N)。

这是正确的解决办法吗？

Answer 1

是的，上面的内容是完全正确的(除了第一行的小例外应该是t(n) = t(n-4) + (n-4)^2 + (n-2)^2，根据问题的定义，并纠正下面的内容--但它不会影响渐近线的结果)。

为了证明这一点，我们可以使用数学归纳法

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 -证明它是作为一个幸灾乐祸。

由此我们可以导出t(n)在O(n^3)中。使用类似的方法，我们可以证明它也在Omega(n^3)中，因此它是Theta(n^3)。

Answer 2

使用这个在线计算器结果可以看到Θ(n^3)。

​

如我所想，右乘法可以创建Θ(n^3)。