+1 Daumen
809 Aufrufe

Aufgabe:

Lösen Sie die Rekurrenzgleichung

$$ \begin{aligned} T(n) &=3 T\left(\frac{n}{3}\right)+n \text { für alle } n \geq 3 \\ T(1) &=1 \end{aligned} $$

mit Hilfe eines Rekursionsbaumes. Nehmen Sie zur Vereinfachung an, dass \( n \) eine Potenz von 3 ist.

von

1 Antwort

+1 Daumen
Mathematisch sicher nicht sauber formuliert, aber ich probiere das mal. Vielleicht kann es ja jemand verbessern und ergänzen.

T(n) = 3 * T(n/3) + n = 2*3 für n = 3

T(n) = 3 * (3 * T(n/9) + n/3) + n = 9 * T(n/9) + 2n = 3*9 für n = 9

T(n) = 9 * (3 * T(n/27) + n/9) + 2n = 27 * T(n/27) + 3n = 4*27 für 9 = 27

.....

T(n) = (log3(n) + 1) * n

T(n) = n * log3(n) + n für eine 3er-Potenz n
von 345 k 🚀

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage sofort und kostenfrei

x
Made by a lovely community