Komplexität des Fisher-Yates-Shuffle-Algorithmus

15

Diese Frage bezieht sich auf den Fisher-Yates-Algorithmus zum Zurückgeben einer zufälligen Mischung eines gegebenen Arrays. Die Wikipedia-Seite sagt, dass ihre Komplexität O (n) ist, aber ich denke, dass es O (n log n) ist.

In jeder Iteration i wird eine zufällige ganze Zahl zwischen 1 und i gewählt. Das einfache Schreiben der Ganzzahl in den Speicher ist O (log i), und da es n Iterationen gibt, ist die Summe gleich

O (log 1) + O (log 2) + ... + O (log n) = O (n log n)

Das ist nicht besser der naive Algorithmus. Vermisse ich hier etwas?

Hinweis: Der naive Algorithmus weist jedem Element eine Zufallszahl im Intervall (0,1) zu und sortiert dann das Array in Bezug auf die zugewiesenen Zahlen.

Tomer Vromen
quelle

Antworten:

24

Ich vermute, dass hier, wie bei den meisten Algorithmen, die Kosten für das Lesen und Schreiben von -Bitzahlen als konstant angenommen werden. Es ist eine kleine Sünde, solange Sie nicht versehentlich mitgerissen werden und P und PSPACE kollabieren .O(logn)

Suresh Venkat
quelle
4
Während dies in der Tat eine "kleine Sünde" ist, denke ich, dass es eine große Sünde der TCS-Pädagogik ist, dass dies niemals explizit erwähnt wird! Jeder einzelne CS-Student entdeckt dies für sich und denkt, dass etwas Wichtiges nicht stimmt, bis ihm gesagt wird, dass jeder das weiß, aber niemand darüber spricht. Gab es nicht vor ein paar Jahren ein Brouhaha, als jemand das O (log n) -Modell ausnutzte, um einen subkubischen Zeitalgorithmus für ein berühmtes Problem zu erhalten, von dem vermutet wurde, dass es Omega (n ^ 3) ist? Wurde das jemals gelöst?
Randomwalker
2
Mir ist nicht bewusst, auf welches brouhaha Sie sich beziehen. Ganz zu schweigen davon, dass Sie definitiv Recht haben. Nachdem ich Jeff Ericksons Post zum ersten Mal gelesen habe, möchte ich jetzt P = PSPACE in meiner Geometrieklasse nur zum Spaß beweisen :)
Suresh Venkat
1
Danke für die Antwort. Ich hätte nie gedacht, dass es so eine große Sache ist. Der Link bietet eine gute Lektüre.
Tomer Vromen
1
Fazit: Machen Sie Ihr Modell immer explizit.
Jukka Suomela
2
Ich denke, der Hauptgrund, warum wir -Bitoperationen als konstante Zeit zulassen, ist, dass Sie (in Polynomialzeit) für die meisten Paare von O ( log n ) -Bitoperanden eine zeitlich konstante Zugriffssuchtabelle programmieren können "moderne" Rechenmodelle. Daran ist nichts "Sündiges" ... für mich ist diese Eigenschaft eine Eigenschaft, die einfach ohne Verlust der Allgemeinheit angenommen werden kann. Ö(Logn)Ö(Logn)
Ryan Williams
17

Das Standardmodell der Berechnung geht davon aus, dass arithmetische Operationen mit O (log n) -Bit-Ganzzahlen in konstanter Zeit ausgeführt werden können, da diese Operationen typischerweise in Hardware übergeben werden. Im Fisher-Yates-Algorithmus dauert das "Schreiben der Ganzzahl i in den Speicher" also nur O (1).

Natürlich ist es durchaus sinnvoll, Algorithmen im Hinblick auf Bitoperationen zu analysieren, aber das Bitkostenmodell ist weniger aussagekräftig für das tatsächliche Verhalten. Sogar die einfache Schleife for i = 1 to n: print(i)erfordert O (n log n) -Bitoperationen.

Jeffε
quelle
Schöner Punkt mit der Schleife. Nie bemerkt, dass ...
Tomer Vromen
8

Dies ist eine Antwort auf "[Fisher-Yates-Algorithmus] ist nicht besser als der naive Algorithmus. Vermisse ich hier etwas?" die du in der frage gestellt hast.

In Ihrem "naiven" Algorithmus, der reelle Zahlen verwendet: Wie viele Bits Genauigkeit verwenden Sie? Wenn Sie die Bitkomplexität zählen (wie es bei Fisher-Yates der Fall zu sein scheint) und der Algorithmus k Zufallsbits für die reellen Zahlen verwendet, beträgt seine Laufzeit Ω (kn log n), da zwei k- Bit-reelle Zahlen benötigen Ω (k) Zeit. Aber k muss mindestens Ω (log n) sein, um zu verhindern, dass zwei Elemente auf dieselbe reelle Zahl abgebildet werden. Dies bedeutet, dass der Algorithmus Ω (n log 2 n) Zeit benötigt, die um a langsamer ist als die Fisher-Yates-Shuffle Faktor von log n.

Wenn Sie nur die Anzahl der Arithmetik- und Vergleichsoperationen zählen und deren Bitkomplexität ignorieren, ist Fisher-Yates Θ (n) und Ihr Algorithmus ist Θ (n log n), immer noch ein Faktor von log n auseinander.

ShreevatsaR
quelle
Ich vermutete, dass der "naive" Algorithmus dieses implizite k hatte ...
Tomer Vromen
1
Der "naive" Algorithmus kann wie folgt in linearer Zeit sauber implementiert werden. Weisen Sie jedem Element eine zufällige Ganzzahl zwischen 1 und n ^ 3 zu und sortieren Sie die Zahlen in O (n) -Zeit über die Radix-Sortierung. (Mit hoher Wahrscheinlichkeit erhalten keine zwei Elemente dieselbe Zufallszahl. Wenn Duplikate vorhanden sind,
mischen Sie
@ JeffE: Danke! Das ist sehr sauber und hat die gleiche Komplexität wie Fisher-Yates. Nachdem ich das gepostet hatte, hatte ich tatsächlich das Gefühl, dass der "naive" Algorithmus nicht schlechter sein sollte ... Ich habe die Tatsache übersehen, dass n k-Bit-Zahlen in O (nk) sortiert werden können, ohne O (nklog n) zu benötigen. Aber ich denke, Knuth-Fisher-Yates ist in den Konstanten noch besser: Es erfordert genau (log n!) Zufallsbits - eine Zufallszahl von 1 bis n, dann 1 bis n-1 usw. - was optimal ist (anstelle von 3n log n), und es kann mit nur konstantem zusätzlichen Speicher an Ort und Stelle durchgeführt werden.
ShreevatsaR
6

Ganzzahlen sind für dieses Problem nichts Besonderes.

Zum Beispiel sind Hash-Tabellen (die beliebige Werte speichern) nicht für den Zugriff auf 0 (1) Zeit, wenn die Hash-Funktion den gesamten Wert lesen muss, um ihren Hash zu berechnen. Für die Darstellung von n eindeutigen Elementen sind durchschnittlich jeweils log n Bits erforderlich, unabhängig davon, wie geschickt Ihre Darstellung ist. Die Berechnung einer Hash-Funktion, die die gesamte Eingabe liest, dauert daher mindestens so lange. In der Praxis sind sie schneller als rot-schwarze Bäume, aber asymptotisch sind sie nicht besser.

Das von randomwalker referenzierte brouhaha handelte von einem POPL 2008-Artikel ( http://portal.acm.org/citation.cfm?doid=1328438.1328460 ), der hier besprochen wurde: http://blog.computationalcomplexity.org/2009/05/shaving- logs-with-unit-cost.html

In diesem Beitrag beschreibt Lance Fortnow, wie er sich als Student beschwert hat, dass das Sortieren wirklich n log ^ 2 n Zeit erfordert, wenn wir alle log n Bits zweier Elemente lesen müssen, um sie zu vergleichen, was ein vernünftiger Einwand ist.

Dave Doty
quelle
Ich verstehe den Autor des Blogposts nicht. Er beschwert sich, dass das Sortieren tatsächlich 0 (n log ^ 2 n) ist, sagt aber dann, dass das Papier fest ist?
Tomer Vromen
Das Papier ist solide (dh nicht falsch), da es ein Modell gibt, in dem arithmetische Operationen Zeit benötigen, und in diesem Modell ist der Algorithmus des Papiers der erste, der o (n ^ 3) -Operationen erzielt.
Dave Doty
Ich erhalte keinen Einwand gegen O (n log ^ 2 n), da die Eingabe selbst bitweise die Größe O (n log n) hat. Übrigens war die Qualität der Kommentare im Komplexitätsblog um einiges höher als ...
Arnab
4

Die Wikipedia-Seite sagt, dass ihre Komplexität O (n) ist, aber ich denke, dass es O (n log n) ist.

Tatsächlich ist O (n log n) eine Untergrenze für dieses Problem in Modellen, in denen die Sortierung O (n log n) ist. Wenn alle Permutationen gleich wahrscheinlich sind, muss der Algorithmus als Funktion von Zufallsströmen zu Permutationen surjektiv sein. Es gibt n! Permutationen, also gibt es in so etwas wie einem Entscheidungsbaummodell Zweige mit einer Länge von mindestens O (log n!) = O (n log n).

1-ϵÖ(ϵ)

Per Vognsen
quelle
3

In TCS berücksichtigen wir - sofern nicht ausdrücklich anders angegeben - die Komplexität einer Turingmaschine. Während dies für theoretische Zwecke in Ordnung ist, sind die Ergebnisse in der Praxis nicht sehr hilfreich, da wir verschiedene Maschinenmodelle (dh endliche Approximationen) in Hardware implementieren. Es ist daher möglich, die Komplexität dieser Modelle zu erfragen. Beispielsweise nehmen wir normalerweise an, dass Registermaschinen (ähnlich wie echte CPUs) atomare Operationen an zwei Registern in konstanter Zeit ausführen können - dies könnte hier verwendet worden sein.

Kurzum: Sie denken in TMs, die Artikelautoren in RMs. Sie haben beide recht.

Raphael
quelle