Average Case Quicksort < Komplex. & Berechnb. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 17:43 So 12.04.2009 | | Autor: | fin129 |
| Aufgabe | | Leiten sie die Average-Case-Laufzeit von Quicksort her. |
Mein Ansatz (mit Hilfe eines Vorlesungsskripts) soweit:
[mm]
V(n) = n-1 + \frac{1}{n} \cdot \sum_{i=1}^{n} (V(n-i) + V(i-1))
= n-1 + \frac{2}{n} \cdot \sum_{i=1}^{n} V(i-1)
[/mm]
Also gilt (1)
[mm]
n\cdot V(n) = n \cdot (n-1) + 2\sum_{i=1}^{n} V(i-1) = n \cdot (n-1) + 2(V(0) + V(1) + \ldots + V(n-2) + V(n-1))
[/mm]
und (2)
[mm]
(n-1)\cdot V(n-1) = (n-1) \cdot (n-2) + 2\sum_{i=1}^{n-1} V(i-1) = (n-1) \cdot (n-2) + 2(V(0) + V(1) + \ldots + V(n-2))
[/mm]
weiter mit (1) - (2):
[mm]
nV(n)-(n-1)V(n-1) = (n-(n-2))(n-1) + 2 V(n-1)
= 2 ((n-1) + V(n-1))
[/mm]
Allerdings sollte da laut Skript rauskommen:
[mm]
nV(n)-(n-1)V(n-1) =2(n-1)
[/mm]
Wo liegt in meiner Rechnung der Fehler?
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 18:20 So 19.04.2009 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
