Sortieralgorithmen < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 17:16 Do 29.05.2008 | | Autor: | info123 |
| Aufgabe | Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
1)Zeigen Sie, daß jeder Sortieralgorithmus, der Elemente jeweils nur um eine Position
bewegt, eine Laufzeit in
[mm] Omega(n^2) [/mm] hat. Dabei bezeichne n die Anzahl der zu
sortierenden Elemente in der Menge.
2)Zeigen Sie: Ein Algorithmus, der nur auf der Basis von Schlüsselvergleichen
arbeitet, benötigt im worst-case mindestens n - 1 Vergleiche, um zwei sortierte
Folgen x1 <= x2<=....<=xn
und y1<= y2<= ....<=yn
zu einer sortierten Folge
z1<=z2<=....<=zn zu verschmelzen. |
Ich würde mich freuen, wenn mir jemand hierbei helfen könnte.
In der Theorie mögen diese Aufgaben nicht so schwer sein, doch
meine Ansätze beruhen leider nur auf Erklärungen.
Ich weiß aber nicht wie ich sie konkret zeigen soll.
Meine Idee bei der 1) war, dass omega ja Best Case bedeutet,
d.h. die Folge ist bereits vorsortiert.
Es werden also lediglich Vergleiche durchgeführt( jedes Element mit jedem): (n*(n-1))/2 [mm] ->n^2 [/mm] Bsp.: Bubblesort
Danke für eure Hilfe
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 21:29 Do 29.05.2008 | | Autor: | Gilga |
http://de.wikipedia.org/wiki/Landau-Symbole
1) war, dass omega ja Best Case bedeutet,
[mm] $\Omega$ [/mm] beschreibt die mindestdauer im worst-case!
Denk mal bei Bubblesort mehr an das bewegen als vergleichen
!! in der Aufagbe 1) steht nichts von Vergleichen.
2)Verschmelz mal 2 sortierte Folgen auf einem Blatt Papier.
Dann kommst du auf die Idee...
|
|
|
|
