Quicksort: Unterschied zwischen den Versionen

Zeile 93:

=== Worst-Case ===

[[Datei:Baum N-Ebenen.png|mini]]

Betrachten wir zunächst die Worst-Case-~~Laufzeitanalyseaufzeit~~. Angenommen, wir haben wirklich Pech und die Partitionsgrößen sind wirklich unausgeglichen. Angenommen, der von der Partitionsfunktion ausgewählte Drehpunkt ist immer entweder das kleinste oder das größte Element im Subarray für n-Elemente. Dann enthält eine der Partitionen keine Elemente und die andere Partition enthält n-1 Elemente - alle außer dem Pivot. Die rekursiven Aufrufe erfolgen also auf Subarrays der Größen 0 und n-1.

Betrachten wir zunächst die Worst-Case-[[Laufzeitanalyse]]. Angenommen, wir haben wirklich Pech und die Partitionsgrößen sind wirklich unausgeglichen. Angenommen, der von der Partitionsfunktion ausgewählte Drehpunkt ist immer entweder das kleinste oder das größte Element im Subarray für n-Elemente. Dann enthält eine der Partitionen keine Elemente und die andere Partition enthält n-1 Elemente - alle außer dem Pivot. Die rekursiven Aufrufe erfolgen also auf Subarrays der Größen 0 und n-1.

In diesem Szenario benötigt [[Rekursion|rekursive]] Aufruf von n-1 Elementen c* (n - 1) für eine Konstante c. Dies Konstante c repräsentiert die Benötigte Zeit für eine Operation wie einen Aufruf oder einen Vergleich. Für n-2 Elemente werden die Zeit c*(n-2) benötigt und so weiter (siehe Abbildung).

@@ Zeile 93: / Zeile 93: @@
 === Worst-Case ===
 [[Datei:Baum N-Ebenen.png|mini]]
-Betrachten wir zunächst die Worst-Case-Laufzeitanalyseaufzeit. Angenommen, wir haben wirklich Pech und die Partitionsgrößen sind wirklich unausgeglichen. Angenommen, der von der Partitionsfunktion ausgewählte Drehpunkt ist immer entweder das kleinste oder das größte Element im Subarray für n-Elemente. Dann enthält eine der Partitionen keine Elemente und die andere Partition enthält n-1 Elemente - alle außer dem Pivot. Die rekursiven Aufrufe erfolgen also auf Subarrays der Größen 0 und n-1.
+Betrachten wir zunächst die Worst-Case-[[Laufzeitanalyse]]. Angenommen, wir haben wirklich Pech und die Partitionsgrößen sind wirklich unausgeglichen. Angenommen, der von der Partitionsfunktion ausgewählte Drehpunkt ist immer entweder das kleinste oder das größte Element im Subarray für n-Elemente. Dann enthält eine der Partitionen keine Elemente und die andere Partition enthält n-1 Elemente - alle außer dem Pivot. Die rekursiven Aufrufe erfolgen also auf Subarrays der Größen 0 und n-1.
 In diesem Szenario benötigt [[Rekursion|rekursive]] Aufruf von n-1  Elementen c* (n - 1) für eine Konstante c. Dies Konstante c repräsentiert die Benötigte Zeit für eine Operation wie einen Aufruf oder einen Vergleich. Für n-2 Elemente werden die Zeit c*(n-2) benötigt und so weiter (siehe Abbildung).