Wiederholungsrelation für Zeitkomplexität

7

ich suche eine Θ Annäherung von

T.(n)=T.(n- -1)+cn2

Das habe ich bisher:

T(n1)=T(n2)+c(n1)2T(n)=T(n2)+c(n1)+cn2T(n2)=T(n3)+c(n2)2T(n)=T(n3)+c(n2)2+c(n1)2+cn2T(n3)=T(n4)+c(n3)2T(n)=T(n4)+c(n3)2+c(n2)2+c(n1)2+cn2

An diesem Punkt wollte ich also verallgemeinern und ersetzen k in die Gleichung.

T.(n)=T.(n- -k)+(n- -(k- -1))2+c(k- -1)2

Jetzt fange ich an, den Basisfall 1 ins Bild zu bringen. Bei einigen früheren, einfacheren Problemen konnte ich meine verallgemeinerte k-Gleichung auf 1 setzen und dann nach lösenk. Dann setzenk zurück in die Gleichung, um meine endgültige Antwort zu erhalten.

Aber ich stecke total auf dem (n- -k+1)2Teil. Ich meine, sollte ich das alles eigentlich vereiteln? Ich habe es getan und bekommenk2- -2kn- -2k+n2+2n+1=1. An diesem Punkt denke ich, dass ich etwas falsch gemacht haben muss, da ich dies in früheren Problemen nie gesehen habe.

Könnte mir jemand Hilfe bei der Lösung dieses Problems anbieten? Ich würde es sehr begrüßen. Ich habe auch einen anderen Ansatz ausprobiert, bei dem ich versucht habe festzulegenn- -k=0 aus dem letzten Teil der Gleichung und bekam das k=n. Ich steckte n gegen Ende wieder in die Gleichung ein und bekam schließlichn2als Antwort. Ich habe keine Ahnung, ob das richtig ist oder nicht.

Ich bin in einer Klasse zur Analyse von Algorithmen und wir haben angefangen, Wiederholungsrelationen durchzuführen. Ich bin mir nicht 100% sicher, ob ich dieses Problem richtig mache. Ich komme zu einem Punkt, an dem ich einfach festsitze und nicht weiß, was ich tun soll. Vielleicht mache ich das falsch, wer weiß. Die Frage kümmert sich nicht um Ober- oder Untergrenzen, sie will nur ein Theta.

Leckere Brownies
quelle
In dieser Frage finden Sie zahlreiche Informationen zum Lösen von Wiederholungen.
Raphael

Antworten:

9

Setzen Sie Ihre Überlegungen einfach wie folgt fort.

T.(n)=T.(n- -1)+cn2=T.(n- -2)+c(n- -1)2+cn2==T.(n- -n)+c(12)+c(22)+cn2=T.(0)+c1ichnich2.

Wissen Sie, wie Sie dies mit der Additionsformel für die erste vereinfachen können? n Quadrate?

PKG
quelle
Ich bin mir nicht ganz sicher, was Sie mit der Additionsformel für die ersten n Quadrate meinen. Ist das wie n (n + 1) / 2 Typ Zeug?
Tastybrownies
Genau das ist richtig
PKG
3

Im Allgemeinen jede Wiederholungsbeziehung der Form T.(n)=T.(n- -1)+f(n) hat die Lösung T.(n)=ich=0nf(ich).

David Richerby
quelle
2

Manchmal sind Formeln schwer zu merken, Integration kann praktisch sein -

ich=1nich21nich2dich=13ich3]]1n=13(n3- -1)cn3=Ö(n3)
Ramgorur
quelle
Ich liebe diese Methode, aber sie gibt dir nichts Ωgebunden.
Pratik Deoghare
2
@PratikDeoghare ja das tut es. weil die Funktionf(ich)=ich2ist monoton.
Igor Shinkar