Θ-notation für die Summe einer geometrischen Reihe

Ich habe eine Frage bezüglich der geometrischen Reihe. Warum ist

1 + c + c2 + ... + cn = Θ(cn)

wenn c > 1? Ich verstehe, warum es ist Θ(n), wenn c = 1, und es ist Θ(1), wenn c < 1, aber ich kann einfach nicht herausfinden, warum es ist Θ(cn), wenn c>1.

Dank!

  • vielleicht haben Sie mehr Glück bei math.stackexchange.com
  • Danke, ich werde versuchen, die Website
  • Diese Frage scheint off-topic, weil es um Mathe.
  • Laufzeit-Berechnung ist nie off-topic, wenn es um gute Programmierung. 🙂
InformationsquelleAutor user308553 | 2012-01-20
  1. 4

    Die Summe der ersten n Glieder der geometrischen Reihe

    c0 + c1 + ... + cn-1

    ist gegeben durch die me

    (cn - 1) /(c - 1)

    Beachten Sie, dass wenn c > 1, dann ist diese Menge begrenzt ist, die von oben durch cn - 1 und von unten durch cn-1 - 1 /c. Also, es ist O - (cn) und Ω(cn), so ist Θ(cn).

    Hoffe, das hilft!

    InformationsquelleAutor templatetypedef
  2. 3

    Lassen c > 1 und g(c) = 1 + c + c2 + ... + cn.

    Das erste, was zu erkennen ist, dass für einige n haben wir S(n) = (cn+1 - 1) /(c - 1), wobei S(n) ist die Summe der Reihe.

    Also haben wir, dass (cn+1 - cn) /(c-1) <= (cn+1 - 1) /(c - 1) = S(n), da cn >= 1.

    Also (cn+1 - cn) /(c-1) = (cn(c-1)) /(c-1) = cn <= S(n)

    Damit haben wir, dass S(n) >= cn.

    Nun, da wir gefunden haben, unsere untere Schranke, schauen wir uns für die Obere Grenze.

    Beachten Sie, dass S(n) = (cn+1 - 1) /(c - 1) <= (cn+1) /(c - 1) = ((cn) c) /(c -1).

    Einfach unsere Sicht der algebra ein bisschen, y = c /(c-1) und setzen es in die Gleichung oben.

    Daher S(n) <= y * cn, wo y ist nur einige Konstante seit c ist! Dies ist eine wichtige Beobachtung, da nun es ist nur ein Vielfaches von cn.

    So, jetzt haben wir uns gefunden unsere Obere Schranke als gut.

    Somit haben wir cn <= S(n) <= y * cn.

    Daher S(n) = Θ(cn), wenn c > 1.

    InformationsquelleAutor Derek W
Schreibe einen Kommentar