Wie lautet die Netto-Laufzeit des folgenden Ausdrucks?

Question

Für einen rekursiven Algorithmus habe ich den folgenden Ausdruck erstellt, um die Laufzeit zu berechnen. Aber ich bin nicht klar, wie dies zu vereinfachen und in Big-O Notation auszudrücken.

Wenn es nur 4k, dann weiß ich, dass es einfach eine GP-Serie ist, und wir können den letzten Term nehmen die 4n als schlimmsten Fall ist die Zeit läuft. Helfen Sie mir hier zu verstehen, wie man mit umgehen kann.

Answer 1

Versuchen Sie einfach den Begriff ein wenig

 
Σk=0,...,n 4k(k+1) < Σk=0,...,n 4k(n+1) = (n+1) Σk=0,...,n 4k 

Das ist also in O(n⋅4n) zu vereinfachen. Und diese Grenze ist eng, da 4n(n+1) Teil der Summe ist.

Hinweis: Was Sie unter "Laufzeit" verstehen, wird normalerweise "Komplexität" genannt.