algorithm - 根 n^3 函数之和的 Θ 复杂度是多少？

Question

函数的复杂度（Θ 版本）是多少

n
∑ = 3 * i ^3/2
i=1

我认为它只是 Θ(n ² )，因为 n ²的增长速度比常数或平方根快，至少这在我看来是直观的。有没有办法正式证明这一点？

Answer 1

让我们考虑更简单的情况Sum[i=1..n](i^(3/2))。

让我们考虑以下积分Integrate[i=(k-0.5)..(k+0.5)](i^(3/2))，其中 k 是正整数。

  Integrate[i=(k-0.5)..(k+0.5)](i^(3/2))
= 2/5 * ((k+0.5)^(5/2) - (k-0.5)^(5/2))

可以证明，对于所有正整数 k：

k^(3/2) < 2/5 * ((k+0.5)^(5/2) - (k-0.5)^(5/2))

当我们尝试通过平方、扩展和分组直到平方根消失来解决时，我们最终会得到40*k^6 - 0.024*k^4 + 0.008*k^2 + 0.0001 = 0，这显然没有真正的解决方案。代入 0 表示 RHS > LHS。

（我不知道是否有更好的方法，但以上是一种证明方法）。

这导致：

k^(3/2) < Integrate[i=(k-0.5)..(k+0.5)](i^(3/2))

从中我们可以得出：

Sum[i=1..n](i^(3/2)) < Integrate[i=(0.5)..(n+0.5)](i^(3/2))

对于所有正整数 n。

我们知道：

  Integrate[i=(0.5)..(n+0.5)](i^(3/2))
= 2/5 * ((n+0.5)^(5/2) - 0.5^(5/2))

所以：

Sum[i=1..n](i^(3/2)) < 2/5 * ((n+0.5)^(5/2) - 0.5^(5/2))
Sum[i=1..n](i^(3/2)) = O(n^(5/2))

---

使用上面相同的技巧，让我们考虑积分0.75 * Integrate[i=(k-0.5)..(k+0.5)](i^(3/2))，其中 k 是某个正整数：

  0.75 * Integrate[i=(k-0.5)..(k+0.5)](i^(3/2))
= 0.75 * 2/5 * ((k+0.5)^(5/2) - (k-0.5)^(5/2))
= 0.3 * ((k+0.5)^(5/2) - (k-0.5)^(5/2))

可以证明，对于所有正整数 k：

k^(3/2) > 0.3 * ((k+0.5)^(5/2) - (k-0.5)^(5/2))

可以以与前面部分所示类似的方式完成证明。或者，您可以通过显示单调性并在 k = 1（域中允许的最小数字）处进行测试来做到这一点。

由此，我们可以得出：

Sum[i=1..n](i^(3/2)) > 0.75 * Integrate[i=(0.5)..(n+0.5)](i^(3/2))

对于所有正整数 n。

我们知道：

  Integrate[i=(0.5)..(n+0.5)](i^(3/2))
= 0.3 * ((n+0.5)^(5/2) - 0.5^(5/2))

所以：

Sum[i=1..n](i^(3/2)) > 0.3 * ((n+0.5)^(5/2) - 0.5^(5/2))
Sum[i=1..n](i^(3/2)) = Omega(n^(5/2))

所以，Sum[i=1..n](i^(3/2)) = Theta(n^(5/2))

注：本帖如被迁移，证明有问题，请删除本帖