Sortieralgorithmus < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 22:50 Sa 10.05.2008 | | Autor: | tima84 |
| Aufgabe | Wir betrachten in dieser Aufgabe ganzzahlige Felder, für die MergeSort eine hohe Anzahl von Feldvergleichen
durchführt.
Für jedes k [mm] \in [/mm] N sei [mm] a^{k} [/mm] ein ganzzahliges Feld der Länge [mm] 2^{k} [/mm] , wobei für jedes i < [mm] 2^{k} [/mm] gilt: Das Feldelement [mm] a_{k} [/mm] [i ] ist die
größte Zahl j [mm] \in [/mm] N, so dass [mm] 2^{j} [/mm] | i+1 gilt.
a) Führen Sie den AlgorithmusMergeSort auf dem Feld a4 aus; geben Sie geeignete Zwischenergebnisse an.
b) Geben Sie einen Terman, der die Anzahl der durchgeführten Feldvergleiche [mm] vonMergeSort(a_{k} [/mm] ) in Abhängigkeit
von k ausdrückt.
c) Versuchen Sie zu zeigen, [mm] dassMergeSort(a_{k} [/mm] ) mehr als (k - [mm] 1)2^{k} [/mm] Feldvergleiche durchführt.
Hinweis: Wenn Sie dies gezeigt haben, ist leicht einzusehen, dass die pessimale Anzahl der von MergeSort für
ein Feld der Länge n durchgeführten Feldvergleiche [mm] omega\infinity [/mm] (n log n) ist. |
Leider hab ich keine ahnung wie ich an die sache rangehen soll
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 09:53 So 11.05.2008 | | Autor: | tut-self |
Was meinst du mit:
Das Feldelement $ [mm] a_{k} [/mm] $ [i ] ist die
größte Zahl j $ [mm] \in [/mm] $ N, so dass $ [mm] 2^{j} [/mm] $ | i+1 gilt.
Also speziell "so dass $ [mm] 2^{j} [/mm] $ | i+1 gilt."?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 21:42 So 11.05.2008 | | Autor: | tima84 |
es heisst [mm] 2^j [/mm] an der stelle i+1, so hab ich das jedenfalls verstanden
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 23:23 Do 15.05.2008 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
