algorithm - ルート n^3 関数の和の Θ 複雑度は?

Question

関数の複雑さ (Θ バージョン) は?

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

^{n 2}は定数または平方根よりも速く成長するため、それは単なる Θ(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))

平方根がなくなるまで 2 乗、展開、グループ化して解こうとすると、 になりますが40*k^6 - 0.024*k^4 + 0.008*k^2 + 0.0001 = 0、これには明らかに真の解はありません。0 を代入すると、RHS > LHS であることを示します。

（より良い方法があるかどうかはわかりませんが、上記は証明する1つの方法です）。

これは次のことにつながります。

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))

注：この投稿が移行された場合、証明に問題がある場合は、この投稿を削除してください