Laufzeit Quicksort

05.05.2009, 13:39	isy	Auf diesen Beitrag antworten »
Laufzeit Quicksort Hallo, ich muss etwas über die Laufzeit von Quciksort schreiben. Nun treten bei mir anscheinend generelle Probleme auf... Als Maß für die Laufzeit wird ja die Gesamtanzahl der benötigten Vergleiche betrachtet... Im worst case sind das (n-1)+(n-2)+(n-3)+...+1 = n*(n-1)/2 Vergleiche. Soweit klar... Warum beträgt dann aber im worst case die Laufzeit O(n^2)??? Ich habe wahrscheinlich ein grundlegendes Problem mit der Notation O... Kann mir das wohl jemand erklären??? Danke und Gruß
05.05.2009, 14:09	AD	Auf diesen Beitrag antworten »
Dann informiere dich doch mal über die Landau-Symbole: So bedeutet $\begin{eqnarray} f(n)\in \mathcal{O}(g(n)) \end{eqnarray}$ , dass es ein $\begin{eqnarray} C>0 \end{eqnarray}$ und $\begin{eqnarray} n_0 \end{eqnarray}$ gibt mit $\begin{eqnarray} \|f(n)\| \leq C\cdot \|g(n)\| \end{eqnarray}$ für alle $\begin{eqnarray} n\geq n_0 \end{eqnarray}$ , oder anders formuliert: Dass der Quotient $\begin{eqnarray} \left\| \frac{f(n)}{g(n)} \right\| \end{eqnarray}$ beschränkt bleibt. Im vorliegenden Fall ist $\begin{eqnarray} f(n) = \frac{n(n-1)}{2} \end{eqnarray}$ und $\begin{eqnarray} g(n)=n^2 \end{eqnarray}$ , der Quotient $\begin{eqnarray} \left\| \frac{f(n)}{g(n)} \right\| = \frac{1}{2} \left( 1 - \frac{1}{n} \right) \end{eqnarray}$ ist dann auch beschränkt, somit ist die Aussage $\begin{eqnarray} \frac{n(n-1)}{2} \in \mathcal{O}(n^2) \end{eqnarray}$ gerechtfertigt.
05.05.2009, 15:57	isy	Auf diesen Beitrag antworten »
Danke!!!! Kappiert
18.05.2009, 09:16	isy	Auf diesen Beitrag antworten »
noch eine Frage LZ Quicksort Hallo, wenn ich die Laufzeit von Quicksort im worst case damit begründe, dass Quicksort (n-1)+(n-2)+...+1 = n(n-1)/2 Vergleiche benötigt und daraus folgt O(n²) wie kann ich dann auf Grundlage der benötigten Vergleiche begründen, dass Quicksort im "best case" eine LZ von O(nlog n) hat? Gruß und Danke schon mal!

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »