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 n --1で制限され^、下からc ^n-1- 1/cで制限されることに注意してください。したがって、O（c ⁿ）とΩ（c ⁿ）であるため、Θ（c ⁿ）になります。

お役に立てれば！

Answer 2

c> 1およびg（c）= 1 + c + c ² + ... +cn^とします。

最初に気付くのは、いくつかのnについて、S（n）=（c ^{n + 1} --1）/（c --1）であるということです。ここで、S（n）は級数の合計です。

したがって、c ^{n > = 1であるため、（c n + 1} --c ⁿ）/（c-1）<=（c ^{n + 1} -1）/（c -1）= S（n）となります。

したがって、（c ^{n + 1} -c ⁿ）/（c-1）=（c ⁿ（c-1））/（c-1）= c ⁿ <= S（n）

^{したがって、S（ n}）> =cnとなります。

下限が見つかったので、上限を探しましょう。

S（n）=（c ^{n + 1} --1）/（c --1）<=（c ^{n + 1}）/（c -1）=（（c ⁿ）c）/（c -1）であることに注意してください。

代数の見方を少し簡単にするために、y = c /（c-1）とし、それを上記の方程式に代入します。

したがって、S（n）<= y * c n^ここで、cは！これは重要な観察です。現在はcnの倍数にすぎないから^です。

これで、上限も見つかりました。

したがって、c ⁿ <= S（n）<= y *cn^となります。

したがって、 c> 1の場合、S（n）=Θ（c ^{n ）です。}