Rekursionsgleichung bestimmen mit O-Notation

Neue Frage »

Hannes02 Auf diesen Beitrag antworten »
Rekursionsgleichung bestimmen mit O-Notation
Meine Frage:
Aufgabe: Lösen Sei die Rekursionsgleichung: T(n) = 3T(n/3) + 3n. Gehen sie von T(0) = T(1) = O(1) aus




Meine Ideen:
Problem/Ansatz: Mein Ansatz ist T(n/3) = 3 * T(n/3/3) + 3n/3 = 3T(n/9) + n

Somit ergibt sich T(n) = 3 * (3T(n/9) + n) + 3n = 9T(n/9)+6n

Noch mal einsetzen: 9* (3T(n/9) + n) + 3n = 27T(n/27) + 12n

Muster erkennen 3k * T(n/3k) + ? *n Ich erkenne das Muster nicht von 3n auf 6n und 12n, müsste dann da 9n rauskommen. Kann mir da jemand helfen, den Fehler zu finden
HAL 9000 Auf diesen Beitrag antworten »

Ansatz ergibt , letzteres kennst du vielleicht (irgendwas mit Logarithmus...).
Ulrich Ruhnau Auf diesen Beitrag antworten »

Zitat:
Original von HAL 9000
, letzteres kennst du vielleicht (irgendwas mit Logarithmus...).

Mit wird wohl schätzungsweise das Gewünschte erfüllt.
Dann ist also



Testen wir das doch mal:

und hier einsetzen





Passt!
HAL 9000 Auf diesen Beitrag antworten »

Genau genommen passt auch



mit einer beliebigen reellen Zahl , aber es ist natürlich richtig, dass für der dominierende Summand ist.


Wenn tatsächlich gelten soll (das zuätzliche O(1) an dieser Stelle hier verstehe ich nicht), folgt daraus allerdings wirklich .
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »