Optimale randomisierte Vergleichssortierung

12

Wir alle kennen also die untere Grenze des Vergleichsbaums von Über die ungünstigste Anzahl von Vergleichen, die mit einem (deterministischen) Vergleichs-Sortieralgorithmus durchgeführt wurden. Dies gilt nicht für die randomisierte Vergleichssortierung (wenn wir die erwarteten Vergleiche für die Worst-Case-Eingabe messen). Zum Beispiel ist für n = 4 die deterministische Untergrenze fünf Vergleiche, aber ein randomisierter Algorithmus (der die Eingabe zufällig permutiert und dann die Zusammenführungssortierung anwendet) mit 4 2 ist besserLog2n!n=4 erwartete Vergleiche für alle Eingaben.423

Das ohne die Obergrenzen gebunden gilt nach wie vor im randomisierten Fall durch ein informationstheoretisches Argument, und es kann leicht auf k + 2 ( n ! - 2 k ) verschärft werden Log2n! Dies folgt, weil es einen optimalen Algorithmus gibt, der die Eingabe zufällig permutiert und dann einen (deterministischen) Entscheidungsbaum anwendet, und der beste Entscheidungsbaum (falls vorhanden) ist einer, in dem sich alle Blätter in zwei aufeinanderfolgenden Ebenen befinden.

k+2(n!-2k)n!, wo k=Log2n!.

Was ist, wenn etwas über die Obergrenzen für dieses Problem bekannt ist? Für alle ist die zufällige Anzahl von Vergleichen (in Erwartung der Eingabe im ungünstigsten Fall für den bestmöglichen Algorithmus) immer strikt besser als der beste deterministische Algorithmus (im Wesentlichen, weil n ! Niemals eine Zweierpotenz ist) . Aber wie viel besser?n>2n!

David Eppstein
quelle
lG(n!)+Ö(n)

Antworten:

4

Da lautet deine Frage: "Was ist bekannt?" Hier ist etwas:

http://arxiv.org/abs/1307.3033

Logn!+cnc

Pat Morin
quelle
nLogn-1,415nnLogn-1,399n
Ich bin kein Experte, der einzige Grund, warum ich darüber Bescheid weiß, ist John Iacono. Ich denke jedoch, dass es mit Schwankungen zu tun hat, die darauf beruhen, wie nahe n (4/3 mal) an einer Potenz von 2 liegt. Wenn Sie sich die Analyse auf Seite 71 hier ansehen, gehen Sie auf link.springer.com/content/pdf /10.1007%2FBF01934989.pdf , die -1.415n-Grenze scheint nur zu gelten, wenn für eine ganze Zahl k n = floor ((4/3) 2 ^ k) ist. Vielleicht ist der in Knuth gebundene -1.329n der beste, der für alle n gilt?
Pat Morin
Es gibt definitiv Schwankungen, aber ich dachte, dass (4/3) 2 ^ k der schlimmste Fall war und es für andere Fälle besser war.
David Eppstein