runtime - 几何级数之和的 Θ 表示法

Question

我有一个关于几何级数的问题。为什么是

1 + c + c ² + ... + c ⁿ = Θ(c ⁿ )

当 c > 1 时？^{我理解为什么如果 c = 1 是 Θ( n} )，如果 c < 1 是 Θ(1)，但我就是不明白为什么如果 c>1 是 Θ(cn)。

谢谢！

Answer 1

几何级数前 n 项之和

c ⁰ + c ¹ + ... + c ^n-1

由数量给出

(c ⁿ - 1) / (c - 1)

请注意，如果 c > 1，则该量从上方以 c ⁿ - 1 为界，从下方以 c ^n-1 - 1 / c 为界。因此，它是 O(c ⁿ ) 和 Ω(c ⁿ )，所以它是 Θ(c ⁿ )。

希望这可以帮助！

Answer 2

令 c > 1 且 g(c) = 1 + c + c ² + ... + c ⁿ。

首先要意识到的是，对于一些 n，我们有 S(n) = (c ⁿ⁺¹ - 1) / (c - 1) 其中 S(n) 是级数之和。

所以我们有 (c ⁿ⁺¹ - c ⁿ ) / (c-1) <= (c ⁿ⁺¹ - 1) / (c - 1) = S(n) 因为 c ⁿ >= 1。

所以 (c ⁿ⁺¹ - c ⁿ ) / (c-1) = (c ⁿ (c-1)) / (c-1) = c ⁿ <= S(n)

因此我们有 S(n) >= c ⁿ。

现在我们已经找到了我们的下限，让我们寻找上限。

观察到 S(n) = (c ⁿ⁺¹ - 1) / (c - 1) <= (c ⁿ⁺¹ ) / (c - 1) = ((c ⁿ ) c) / (c -1)。

为了稍微简化我们对代数的看法，让 y = c / (c-1) 并将其代入上述等式。

因此，S(n) <= y * c ⁿ其中y只是某个常数，因为c是！这是一个重要的观察，因为现在它只是 c ⁿ的倍数。

所以现在我们也找到了我们的上限。

因此我们有 c ⁿ <= S(n) <= y * c ⁿ。

因此，当 c > 1 时，S(n) = Θ(cn ^{) 。}