Rekursionsgleichung bestimmen mit O-Notation

27.05.2023, 11:34

Hannes02

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

27.05.2023, 11:45

HAL 9000

Auf diesen Beitrag antworten »

Ansatz $\begin{eqnarray*} T(n) = 3n\cdot S(n) \end{eqnarray*}$ ergibt $\begin{eqnarray*} S(n) = S\left(\frac{n}{3}\right) + 1 \end{eqnarray*}$ , letzteres kennst du vielleicht (irgendwas mit Logarithmus...).

27.05.2023, 21:17

Ulrich Ruhnau

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000
$\begin{eqnarray*} S(n) = S\left(\frac{n}{3}\right) + 1 \end{eqnarray*}$ , letzteres kennst du vielleicht (irgendwas mit Logarithmus...).

Mit $\begin{eqnarray*} S(n)=\log_3n \end{eqnarray*}$ wird wohl schätzungsweise das Gewünschte erfüllt.
Dann ist also

$\begin{eqnarray*} T(n)=3n\cdot S(n)=3n\log_3 n \end{eqnarray*}$

Testen wir das doch mal:

$\begin{eqnarray*} T(n)=3T\left(\frac n3\right)+3n \end{eqnarray*}$ und hier einsetzen

$\begin{eqnarray*} 3n\log_3 n=3\cdot \bcancel{3}\left(\frac n{\bcancel{3}}\right)\log_3 \left(\frac n3\right)+3n<br /> \end{eqnarray*}$

$\begin{eqnarray*} 3n\log_3 n=3n\left(\log_3 n-1\right)+3n \end{eqnarray*}$

Passt!

28.05.2023, 17:47

HAL 9000

Auf diesen Beitrag antworten »

Genau genommen passt auch

$\begin{eqnarray*} T(n) = 3n\log_3(n) + Cn \end{eqnarray*}$

mit einer beliebigen reellen Zahl $\begin{eqnarray*} C \end{eqnarray*}$ , aber es ist natürlich richtig, dass $\begin{eqnarray*} 3n\log_3(n) \end{eqnarray*}$ für $\begin{eqnarray*} n\to\infty \end{eqnarray*}$ der dominierende Summand ist.

Wenn tatsächlich $\begin{eqnarray*} T(0)=T(1) \end{eqnarray*}$ gelten soll (das zuätzliche O(1) an dieser Stelle hier verstehe ich nicht), folgt daraus allerdings wirklich $\begin{eqnarray*} C=0 \end{eqnarray*}$ .

Neue Frage »

Antworten »

Rekursionsgleichung bestimmen mit O-Notation

Verwandte Themen