algorithm - S(n) Big Oh 的简单函数

Question

给出一个简单的函数 f(n)，使得和 S(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)。