algorithm - S(n) Big Oh の簡単な関数

Question

合計 S(n) が Θ(f(n)) になるような単純な関数 f(n) を与えます。

これをどこから始めればよいかわかりません。Big Oh と Big Theta の定義は知っていますが、Sum S(n) から関数を定式化する方法がわかりません。

Answer 1

1. ∑ i^5 < n * n^5 =n^6
2. ∑ i^5 > n/2 * (n/2)^5 = n^6 / 64

1,2 → ∑ i^5 ∈ Θ(n^6) (3)

(3)→ ∑ i^5 * n^2 ∈ Θ(n^8)

Answer 2

この合計は簡単に概算できるだけでなく、Faulhaber の公式を使用して実際に正確に計算することもできます。

それを使用すると、次のようになります。

、これを掛ける必要がありますn^2。したがって、複雑さはO(n^8)です。