Rekursionsgleichungen mit Summen

Question

Aufgabe:

Bestimme eine Lösung der folgenden Rekursionsgleichungen in Θ-Notation. Gehe davon aus, dass n eine Potenz von 2 ist.

T (0) = 2,  T (n) = T (N-2) + n - 1

Problem/Ansatz:

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

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

= T (n - 4) + n  - 3 + n - 1

= T (0) + \( \sum\limits_{i=1}^{\frac{n}{2}}{2i - 1} \)

= 2 + (n/2)²

Ich verstehe hier nicht, wie man von T (n - 4) + n - 3 + n -1 auf T (0) + die Summenform gekommen ist. Wieso n/2?

Analog dazu eine ähnliche Aufgabe:

T (0) = 0   T (n) = 2 * T (n - 4) +1

Problem/Ansatz:

T (n) = 2 * T (n - 4) + 1

= 2 * (2 * T (n - 4) - 4) + 1) + 1

= 2 * 2 * T (n - 8) + 1) + 1)

= 2 * 2 * (2 T (n - 8 - 4) + 1) +1) + 1)

= 2 * 2 * 2  T (n - 12) + 1) + 1) + 1)

= 2³ * T (n - 3 * 4) + \( \sum\limits_{i=0}^{3-1}{2i} \)

=\( 2^{\frac{n}{4}} \) * T (0) + \( \sum\limits_{i=0}^{\frac{n}{4}-1}{2i} \)

= 0 + \( 2^{\frac{n}{4}-1+1} \) - 1

\( 2^{\frac{n}{4}} \) -1

Hier verstehe ich ebenfalls, ab der Stelle wo das Summenzeichen in Erscheinung tritt, nicht wie umgeformt wurde. Die 2³ kommen daher, dass man 2 * 2 *2 vor dem T hat. Die 12 wird (warum auch immer) zu 3 *4 umgeschrieben. Aber wie kommt man auf \( \sum\limits_{i=0}^{3-1}{2i} \) und warum startet die Summe jetzt bei i=0 und nicht, wie bei der oberen Aufgaben, bei i = 1?

Würde mich über eine Erklärung freuen. :)

LG
Marceline, The Vampire Queen

Comments

Rekursionsgleichungen in Θ-Notation.

Wie möchtest du das gelesen haben? Ist Gross-Theta-Notation gemeint?

Answer 1

Hallo Marceline. Das geht auch ohne LGS

Dazu analysierst du zunächst die ersten Zahlen der Folge T(n) und suchst nach einer Struktur

T(2) = T(0) + (2) - 1
T(4) = T(2) + 4 - 1 = (T(0) + 2 - 1) + 4 - 1 = T(0) + (2 + 4) - 2
T(6) = T(4) + 6 - 1 = ((T(0) + 2 - 1) + 4 - 1) + 6 - 1 = T(0) + (2 + 4 + 6) - 3
T(8) = T(6) + 8 - 1 = (((T(0) + 2 - 1) + 4 - 1) + 6 - 1) + 8 - 1 = T(0) + (2 + 4 + 6 + 8) - 4

Nachdem du jetzt die allgemeine Struktur erkannt hast stellst du sie allgemein auf

T(2·n) = T(0) + ∑(k = 1 bis n) (2·k) - n = 2 + n·(n + 1) - n = n^2 + 2
oder eben
T(n) = (n/2)^2 + 2

Siehst du das wie man allgemein vorgehen kann? Ich habe also das was ihr im Unterricht gemacht habt nur eben mit den tatsächlichen ersten Werten gemacht.

Du könntest jetzt noch mit der vollständigen Induktion den Nachweis führen, das der explizite Term richtig ist.

Comments

Sollte n nicht eine Potenz von 2 sein?

---

Sollte n nicht eine Potenz von 2 sein?

Warum das gesagt wird ist mir nicht ganz klar. Es wird ja auch nicht in der Musterlösung benutzt. Es macht ja auch nur Sinn das n eine gerade Zahl ist. Also ein Vielfaches von 2.

Das macht ja auch nur Sinn anhand der Definition.

Ansonsten müsste T(n) irgendwie von T(n/2) abhängen, wenn n eine Zweierpotenz sein soll oder nicht?

Wenn du der Meinung bist das n eine Zweierpotenz sein soll bzw. man davon ausgehen soll, würde ich mich über eine Stellungnahme freuen.

Answer 2

T (0) = 2,  T (n) = T (n-2) + n - 1

Dann gilt

T(2)	T(4)	T(6)	T(8)
3	6	11	18

erste Differenzenfolge 3, 5, 7

zweite Differenzenfolge 2, 2

Da die zweite Diffrerenzenfolge konstant ist, lautet der Ansatz

T(n)=an²+bn+c

Nach Einsetzen der ersten drei Wertepaare aus der Wertetabelle:

3=4a+2b+c

6=16a+4b+c

11=36a+6b+c

Dies System hat die Lösungen a=1/4; b=0; c=2

Dann ist T(n)=n²/4+2=2+(n/2)²(was zu zeigen war).

Comments

Danke für die Antwort, Roland.

Wie genau kommt man bei T (2) auf 3?

Wenn man 2 in die Gleichung einsetzt, müsste da doch stehen T (2-2) + 2 - 1 = 0.

Gibt es eventuell noch einen anderen Weg als ein LGS aufzustellen?

---

Wenn man 2 in die Gleichung einsetzt, müsste da doch stehen T(2) = (2-2) + 2 - 1 = T(0) + 2 -1 = 2 + 2 - 1 = 3

                                          T (0) = 2