Rekursionsgleichung beim Algorithmus

20.05.2023, 11:58

leon02

Rekursionsgleichung beim Algorithmus

Meine Frage:
Aufgabe: Es soll ein Turniermodus betrachtet werden. Dazu werden in der ersten Runde, immer zwei benachbarte Zahlen miteinander verglichen. Die kleinere ?gewinnt? und kommt in die nächste Runde. In dieser Art und Weise werden die Zahlen weiter verglichen, bis nach der letzten Runde nur noch eine Zahl übrig ist.

Stellen Sie eine Rekursionsgleichung auf und analysieren Sie die Laufzeit des Algorithmus

Meine Ideen:
Problem/Ansatz:

T(0) = 0, T(1) = 0, T(2) = 1

Meine Idee: T(n) = T(n/2) + n/2
?> mehrmals Einsetzen um Muster zu erkennen
= T(n/4) + n
= T(n/8) + 1,5n
= T(n/16) + 2n

= T(n/2k) + k*n/2. wann ist n/2k <= 1
T(n) = T(n/2log(n)) + (log(n)*n/2)
T(n) = T(1) + (log(n)*n/2)
T(n) = 0 + (log(n)*n/2)

Aber irgendwie klappt das nicht, kann mir da jemand helfen

20.05.2023, 13:23

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von leon02
Meine Idee: T(n) = T(n/2) + n/2
?> mehrmals Einsetzen um Muster zu erkennen

Bis hierhin Ok. Dann setzt du aber leider falsch ein, denn es ist ja dann
$\begin{eqnarray*} T\left(\frac{n}{2}\right) = T\left(\frac{n}{4}\right) + \frac{\frac{n}{2}}{2} = T\left(\frac{n}{4}\right) + \frac{n}{4} \end{eqnarray*}$

$\begin{eqnarray*} T\left(\frac{n}{4}\right) = T\left(\frac{n}{8}\right) + \frac{\frac{n}{4}}{2} = T\left(\frac{n}{8}\right) + \frac{n}{8} \end{eqnarray*}$
usw. gelten.

Daher lautet die korrekte Rechnung

$\begin{eqnarray*} T(n) = T\left(\frac{n}{2}\right) + \frac{n}{2} = T\left(\frac{n}{4}\right) + \frac{3}{4}n = T\left(\frac{n}{8}\right) + \frac{7}{8}n = \ldots \end{eqnarray*}$

Stimmt genau genommen exakt bis zum Ende nur für Zweierpotenzen $\begin{eqnarray*} n \end{eqnarray*}$ .

Übrigens: Dein $\begin{eqnarray*} T(n) \end{eqnarray*}$ entspricht ja der Spielanzahl, um in einem reinem KO-Turnier mit $\begin{eqnarray*} n \end{eqnarray*}$ Teilnehmern einen Sieger zu ermitteln. Auch für Nicht-Zweierpotenzen $\begin{eqnarray*} n \end{eqnarray*}$ ergibt sich hier immer $\begin{eqnarray*} T(n)=n-1 \end{eqnarray*}$ , denn in jedem Spiel wird genau ein Teilnehmer eliminiert, es braucht damit genau $\begin{eqnarray*} n-1 \end{eqnarray*}$ Spiele, um von n schrittweise bis zu einem Teilnehmer (dem Sieger) zu reduzieren. Augenzwinkern

Neue Frage »

Antworten »

Rekursionsgleichung beim Algorithmus

Verwandte Themen