scientific article; zbMATH DE number 1052336

From MaRDI portal
Publication:4349938





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.











This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4349938)