Vergleichsbasier Algorithmus < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 12:12 So 20.02.2011 | | Autor: | hilado |
| Aufgabe | | Beweisen Sie, dass ein vergleichsbasierter Algorithmus zur Bestimmung des Maximums von n Elementen mindestens n - 1 Vergleiche benötigt. |
Ich hab hier mal einen Text dazu geschrieben:
In einer unsortierten Menge von Zahlen setzen wir das erste als die Maximalszahl. Nun vergleichen wir diese Maximalzahl mit jeder anderen Zahl in dieser unsortierten Menge. Falls eine Zahl auftaucht die größer ist als die aktuelle Maximalzahl, so setzen wir die neue Zahl als neue Maximalzahl. Da die Reihe unsortiert ist, kann es sein, dass die größte Zahl am Schluss auftaucht. Deshalb brauchen wir n-1 Vergleiche.
Kann ich das so hinschreiben? Oder wie soll so ein Beweis aussehen?
|
|
| |
|
> Beweisen Sie, dass ein vergleichsbasierter Algorithmus zur
> Bestimmung des Maximums von n Elementen mindestens n - 1
> Vergleiche benötigt.
> Ich hab hier mal einen Text dazu geschrieben:
>
> In einer unsortierten Menge von Zahlen setzen wir das erste
> als die Maximalszahl. Nun vergleichen wir diese Maximalzahl
> mit jeder anderen Zahl in dieser unsortierten Menge. Falls
> eine Zahl auftaucht die größer ist als die aktuelle
> Maximalzahl, so setzen wir die neue Zahl als neue
> Maximalzahl. Da die Reihe unsortiert ist, kann es sein,
> dass die größte Zahl am Schluss auftaucht. Deshalb
> brauchen wir n-1 Vergleiche.
>
> Kann ich das so hinschreiben? Oder wie soll so ein Beweis
> aussehen?
Hallo,
das Problem deines Beweises ist, dass du einen speziellen Algorithmus betrachtest, der im Worst Case n-1 Schlüsselvergleiche benötigt. Es sollte aber auch allgemein klar werden.
Die zu beweisende Aussage ist eigentlich trivial und daher nicht einfach zu formulieren.
Mein Vorschlag:
Für das Maximum muss gelten, dass es größer als alle anderen n-1 Elemente ist. Da die Menge ungeordnet ist, muss ein Algorithmus für das Problem alle anderen Elemente mit dem Maximum m in Relation bringen. Das kann wie bei deinem Algorithmus auch indirekt passieren. (Damit meine ich, wenn beim Vergleich zweier Elemente [mm] a,b\neq [/mm] m ohne Einschränkung a<b gilt und der Algorithmus später überprüft b<m, so ist wegen Transitivität der < Relation auch a<m). Letztendlich müssen aber auf jeden Fall n-1 Schlüsselvergleiche stattfinden.
Gruß
|
|
|
|
