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.
