algorithm - 运行时间 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²

...因为它减少了 2，所以它大约有 n/2 项，并且通过扩展我们拥有的所有正方形 (n/2) * (n²)，它等于 n³。所以运行时间是theta(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)。