0 Daumen
279 Aufrufe

Aufgabe:

blob.png

Text erkannt:

Frage 2.c: \( \quad \) Der Median von \( n \) Zahlen lässt sich in \( O(n) \) Zeit finden. Geben Sie für ein abgewandeltes Quicksort-Verfahren, das immer den Median als Pivot-Element benutzt, die Laufzeit als Rekurrenzgleichung an und lösen Sie diese unter Zuhilfenahme des Mastertheorems! Gehen Sie davon aus, dass lauter unter-
schiedliche Zahlen eingegeben werden.


Problem:

Hallu! :-)

kann mir hier jemand helfen? Ich absolut keine Ahnung wie ich hier am besten die Laufzeit berechne...

Avatar von

Du brauchst überhaupt nicht am besten die Laufzeit berechnen. Es reicht wenn du auf irgendeinem mathematisch korrekten Weg die Laufzeit berechnest.

Aber wie soll das genau funktionieren? Wäre das hier ein Ansatz?


T(n) = 2T(n/2) + Theta(n)?

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community