vergleichbas. Sortierverfahren < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | | Zeige, dass es KEIN vergleichbasiertes Sortierverfahren gibt, das mind. die Hälfte der n! möglichen Eingaben der Länge n in linearer Zeit sortiert. Gibt es ein Verfahren, das jede nte Eingaben der Länge n in linearer Zeit sortiert? Oder wenigstens jede [mm] 2^{n}te? [/mm] |
Hallo,
ich sitz voll verzweifelt an dieser Aufgabe und weiß überhaupt nicht, wie ich das zeigen soll. Ich versteh nicht richtig, was ich da machen muss.
Daher hoff ich, dass mir jemand weiter helfen kann. Wie muss ich denn da vorgehen.
Ich würde gerne einen Lösungsansatz posten, aber leider weiß ich überhaupt nicht, was ich tun muss....
Ich hoffe trotzdem, dass mir jemand helfen wird.
Viele Grüße,
wetterfrosch
|
|
| |
|
Hallo und guten Morgen,
also ein Verfahren, das die Hälfte aller Permutationen der Länge n in Zeit = Anz. Vergleiche [mm] \leq c\cdot [/mm] n
sortiert, müsste aber dann mit höchstens [mm] c\cdot [/mm] n Vergleichen mindestens [mm] \frac{n!}{2} [/mm] Permutationen unterscheiden.
Es ist jedoch n! größenordnungsmäßig sowas wie [mm] 2^{n\cdot \log n}, [/mm] während man mit [mm] c\cdot [/mm] n Vergleichen natürlich nur
höchstens [mm] 2^{c\cdot n}=o(2^{n\cdot \log n}) [/mm] Permutationen unterscheiden kann.
Analog kannst Du die restlichen Fragestellungen angehen.
Viele Grüße,
Mathias
|
|
|
|
