Sortieren einer Folge < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 16:30 Sa 17.06.2006 | | Autor: | Fahnder |
| Aufgabe | | Zeigen Sie, dass das Sortieren einer Folge a der Länge N mittels Quicksort im Best Case die Laufzeit Tmin(N) = (N · logN) hat. |
Hi,
also kann mir jemand mal sagen, was man darunter versteht? Also ich habe keine Ahnung was ich da machen soll.
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Ich danke im Voraus
|
|
| |
|
Hallo!
> Zeigen Sie, dass das Sortieren einer Folge a der Länge N
> mittels Quicksort im Best Case die Laufzeit Tmin(N) = (N ·
> logN) hat.
> Hi,
> also kann mir jemand mal sagen, was man darunter versteht?
> Also ich habe keine Ahnung was ich da machen soll.
Du verstehst also nur die Aufgabenstellung nicht!?
Das ist doch recht einfach:
Wenn du ohne irgendeinen Algorithmus sondern einfach mit dem normalen Menschenverstand eine Folge von Zahlen sortieren sollst, und die Folge schon sortiert ist, dann brauchst du gar nichts zu machen. Das hätte dann also z. B. die Laufzeit 0, oder von mir aus auch 1, wenn du das "angucken der Folge" als Zeit zählen möchtest. Wenn du Folge jetzt zum Beispiel absteigend sortiert ist, du sie aber aufsteigend sortieren sollst, dann müsstest du nichts anderes machen, als sie "umzudrehen".
Und was ist der beste Fall für Quicksort? Naja, was macht Quicksort? Es nimmt sich ein Pivotelement und schmeißt alle Elemente, die kleiner sind nach links und alle, die größer sind, nach rechts. Wenn du dabei anfangs eine sortierte Folge hast, geht das mit Quicksort nicht so schnell, wenn du z. B. das erste Element als Pivotelement wählst. Denn dann wird quasi jedes Element einmal als Pivotelement gewählt, weil alle Elemente größer sind und somit auf die selbe Seite geschmissten werden. Du hättest also N Pivotelemente.
Am besten wäre es, wenn du immer ein Pivotelement erwischst, sodass links und rechts genauso viele Elemente stehen. Und du sollst nun zeigen, dass genau dann die Laufzeit [mm] $N*\log [/mm] N$ rauskommt.
Viele Grüße
Bastiane
![[cap]](/images/smileys/cap.gif "[cap]")
|
|
|
|
