0 Daumen
372 Aufrufe

Sei \( n=4^{k} \) :

\( T(n)=\left\{\begin{array}{cc} c & \text { falls } n=1 \\ 3 T\left(\frac{n}{4}\right)+n & \text { falls } n>1 \end{array}\right. \)


Kann mir das mit dem Master Theorem erklären aber wie löse ich das per Induktion ?

Avatar von

Hallo

Was ist die Aufgabe? suchst du eine explizite Darstellung von T(n) und hast die gefunden und willst sie per Induktion beweisen, dann ist das doch einfach In T(n+1) T(n) einsetzen  und zeigen dass deine geratene Formel stimmt.

lul

Ja wir suchen eine geschlossene Form für T(n) durch substituieren :)

Hallo

hast du ne Formel und willst sie beweisen oder suchst du die Formel?

was heisst:"Kann mir das mit dem Master Theorem erklären"

schreib die ersten T(4^0) bis T(4^4) hin und sieh ob du dann auf 4^n verallgemeinern kannst.

Gruß lul

Ich soll diese Gleichung beweisen und das am besten per Induktion xD

Hallo

dann schreib deine Gleichung mal hin.

lul

also mit n+1 gelange ich dann zu


T(n+1) = 3T (4^k+1 / 4) + 4^k+1

Hallo
das ist ja die Rekursionsformel, was du beweisen sollst ist, dass die explizite Formel diesem Gesetz folgt. die Rekursionsfolge ist gegeben, die kann man nicht beweisen.
Hast du nun versucht eine explizite Formel zu finden?
Gruß lul

Mit   α = log4 3   wird   T(n)  =  nα·(c-4) + 4n

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community