Rekursionsgleichung beim Algorithmus

Question

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.

Problem/Ansatz:

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

T(n) = T(n/2) + n/2
= T(n/4) + n
= T(n/8) + 1,5n
= T(n/16) + 2n

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

T(n) = 0 + log…

Aber irgendwie klappt das nicht, kann mir da jemand helfen

Comments

Beschreibe erst mal die Aufgabenstellung verständlich. Geht es um die natürlichen Zahlen von 1 bis n?

Wenn ja: Vergleicht man 1 und 2, kommt 1 in die nächste Runde, und 2 fliegt raus.

Fängt man jedoch damit an, 2 mit 3 zu vergleichen, kommt 2 in die nächste Runde...

Oder geht es vielleicht um irgendeine Zahlenfolge wie

17, 3, 22, 24, 2, 999, ...

und das was du "benachbarte Zahlen" nennst, sind in Wirklichkeit benachbarte Folgenglieder?

---

So ist unsere Aufgabenstellung, es ist ein Turnier, also denke mal man gibt irgendwelche Zahlen ein und dann werden sie verglichen also wie 1 8 5 7 9 0, dann 1 8, 5 7, 9 0, dann 1, 5, 0, dann 1 5, also 1, 0 und letztlich 0, also sind es ja n-1 Vergleiche, aber wir sollen das als Rekursionsgleichung betrachten

---

Du solltest vielleicht auch schreiben das es dabei geht das Laufzeitverhalten des Turniers zu beschreiben.

---

Aber das impliziert doch die Aufgabenstellung

---

Was ist denn deine Rekursionsgleichung?  In jedem Schritt wird die Zahl der Eintrage halbiert?  im ersten Schritt hat man n /2 Vergleiche, im nächsten n/4 usw. bis n/2^n=1

Gruß lul

---

Ja danke, habe es jetzt schon selber hinbekommen, trotzdem danke

---

Ja, du hast es bei Mathe board.de selber hinbekommen.