No label defined (Q4349938)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 1052336
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 1052336 |
Statements
26 August 1997
0 references
stochastic analysis of the quicksort algorithm
0 references
0.8657243251800537
0 references
0.8225759267807007
0 references
0.8042247295379639
0 references
0.7971964478492737
0 references
0.7957296967506409
0 references
Ausgehend von der Analyse der Anzahl der Vergleiche \(X_n\), die Varianten des bekannten Sortieralgorithmus Quicksort zum Sortieren einer Liste der Länge \(n\) benötigen, erhalten wir folgendes allgemeine Resultat: Betrachte Folgen von Zufallsvariablen \((X_n)_{n\in\mathbb{Z}^+}\) und \((\overline X_n)_{n\in\mathbb{Z}^+}\) mit Werten in \(\mathbb{Z}^+\), und \((Z_n)_{n\geq n_0}\) mit Werten jeweils in \(\{1,\dots,n\}\). Die \(X_n\) und die \(\overline X_n\) seien jeweils identisch verteilt, sämtliche Zufallsvariablen seien unabhängig. Die Verteilung von \(Z_n/n\) konvergiere gegen ein Maß auf \([0,1]\). Für \(n\geq n_0\) seien die Verteilungen der \(X_n\) rekursiv gegeben durch \(L(X_n)= L(X_{Z_n-1}+\overline X_{n-Z_n}+n)\). Wir zeigen, daß unter allgemein gehaltenen Voraussetzungen \((X_n- \text{E}X_n)/n\) schwach gegen eine Zufallsvariable \(Y\) konvergiert, deren Verteilung Fixpunkt einer Kontraktion ist. Man erhält daraus die Abschätzung \[ \text{P}(|X_n- \text{E}X_n|\geq\varepsilon \text{E}X_n)\leq\text{Const }n^{-2\varepsilon}. \] Bei der zur Herleitung des Resultates durchgeführten Untersuchung der Erwartungswerte \(\text{E}X_n\) erhalten wir ein weiteres allgemeines Resultat: Sei \(\{\mu_n\}_{n\geq n_0}\) eine Folge von Wahrscheinlichkeitsmaßen jeweils auf der Menge \(\{1/n,2/n,\dots,(n-1)/n\}\), die schwach gegen ein Wahrscheinlichkeitsmaß \(\mu\) auf \([0,1]\) konvergiert. Weiter seien \(a\) und \(c\) Funktionen von \(\mathbb{N}\) nach \(\mathbb{R}\), und für \(n\geq n_0\) gelte die Rekursionsgleichung \(a(n)= \sum^{n-1}_{n=1}\mu_n(k/n)a(k)+ c(n)\). Wir zeigen: Ist \(c\) von beschränkter Variation und \(\int^\infty_{n_0} c(s)/s ds=\infty\), so gilt \(a(n)\cong\text{const }\int^n_{n_0} c(s)/s ds\), ist \(|c|\) monoton fallend und \(\int^\infty_{n_0}|c(s)|/s ds\) endlich, so existiert \(\lim a(n)\) und ist endlich. Zum Beweis dieses Ergebnisses konstruieren wir einen speziellen Markov-Prozeß und verwenden Ergebnisse aus der Erneuerungstheorie. Unter gewissen Voraussetzungen gilt es in der Literatur als gesichert, daß für alle Quicksort-Varianten \(\text{E}X_n=\text{const }n\ln n+\text{rest}(n)\), mit \(\text{rest}(n)/n\), beschränkt, gilt. Wir geben eine Variante an, für die unser Resultat \(\text{rest}(n)/n\to\infty\) liefert.
0 references