Wie lösen: T (n) = T (n - 1) + n

Question

Ich habe folgende ausgearbeitet:

T(n) = T(n - 1) + n = O(n^2)

Nun, wenn ich diese Arbeit heraus, dass ich finde, dass die gebundene sehr locker ist. Habe ich etwas falsch gemacht oder ist es nur auf diese Weise?

Answer 1

Denken auf diese Weise davon:
In jeder "Iteration" der Rekursion tun Sie O (n) Arbeit.
Jede Iteration n-1 hat Arbeit zu tun, bis n = Basisfall. (Ich gehe davon aus Fallbasis ist O (n) Arbeit)
Daher ist eine Konstante unabhängig von dem n Basisfall vorausgesetzt, es gibt O (N) Iterationen der Rekursion.
Wenn Sie n Iterationen von O (n) Arbeit jeweils O (n) * O (n) = O (n ^ 2).
Ihre Analyse ist richtig. Falls Sie weitere Informationen über diese Art und Weise zu lösen, Rekursion, Blick in Rekursion Bäume gefällt. Sie sind sehr intuitiv im Vergleich zu den anderen Methoden.

Answer 2

Sie müssen auch ein Basisfall für Ihre Rekursion.

T(1) = c
T(n) = T(n-1) + n

Um dies zu lösen, können Sie zuerst eine Lösung erraten und dann beweisen, dass es funktioniert Induktion.

T(n) = (n + 1) * n / 2 + c - 1

Zuerst wird der Basisfall. Wenn n = 1 ergibt dies c je nach Bedarf.

Für andere n:

  T(n)
= (n + 1) * n / 2 + c - 1
= ((n - 1) + 2) * n / 2 + c - 1
= ((n - 1) * n / 2) + (2 * n / 2) + c - 1
= (n * (n - 1) / 2) + c - 1) + (2 * n / 2)
= T(n - 1) + n

So ist die Lösung funktioniert.

Um die Vermutung an erster Stelle zu bekommen, bemerkt, dass Ihre Wiederholung Beziehung erzeugt die Dreieckszahlen wenn c = 1:

T(1) = 1:

*

T(2) = 3:

*
**

T(3) = 6:

*
**
***

T(4) = 10:

*
**
***
****

etc..

Intuitiv ist ein Dreieck etwa die Hälfte eines Quadrats, und in Big-O-Notation die Konstanten können ignoriert werden, um O (n ^ 2) ist das erwartete Ergebnis.

Answer 3

Die Lösung ist recht einfach für diese ein. Sie haben die Rekursion entrollen:

T(n) = T(n-1) + n = T(n-2) + (n - 1) + n = 
= T(n-3) + (n-2) + (n-1) + n = ... =
= T(0) + 1 + 2 + ... + (n-1) + n 

Sie haben hier arithmetische Progression und die Summe ist 1/2*n*(n-1). Technisch sind Sie nicht die Randbedingung hier, aber mit jeder konstanten Randbedingung sehen Sie, dass die Rekursion O(n^2) ist.

Answer 4

Sieht aus über rechts, wird aber auf dem Basisfall T abhängig (1). Angenommen, Sie tun n Schritte, um T (n) bis T (0) und jedes Mal, wenn der n Begriff irgendwo zwischen 0 und n für einen Durchschnitt von n / 2 so n * n / 2 = (n ^ 2) / 2 = O (n ^ 2).