0 Daumen
38 Aufrufe

Hallo,

ich versuche aktuell für T(n) die folgenden Fragen zu beantworten:

- Wie viele Knoten sind auf Lage i?

- Wie groß ist das n auf Lage i?

- Wie viel Zeit kostet ein Knoten in Lage i?

\( T(n)=\left\{\begin{array}{l|l}1 & n=1 \\ 4 \cdot T\left(\frac{n}{3}\right)+n^{2} \log n & \text { sonst }\end{array}\right. \)

Basierend auf der folgenden Verallgemeinerung:

\( T(n)=\left\{\begin{array}{ll}\Theta(1) & \text { wenn } n=1 \\ a \cdot T\left(\frac{n}{b}\right)+\Theta\left(n^{c}\right) & \text { wenn } n>1\end{array}\right. \)

bin ich bis jetzt soweit gekommen:

- Wie viele Knoten sind auf Lage i? \( 4^{i} \)

- Wie groß ist das n auf Lage i? \( \frac{n}{3i} \)

- Wie viel Zeit kostet ein Knoten in Lage i? Hier liegt mein Problem.

Mir ist bewusst, dass ich für die letzte Frage einfach beantworten kann, indem ich

\( a^{i} \cdot \frac{n^{c}}{b^{c i}} \)

berechne. Ich habe allerdings Probleme, mein c zu definieren. In vorherigen Aufgaben, indenen \( \Theta(n^{c}) = n^{2} \) war habe ich z.B. c = 2 gesetzt. In diesem Fall fällt mir allerdings kein Weg ein, mein c zu bestimmen.




von

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community