Finden des k'th kleinsten Elements aus einer gegebenen Sequenz nur mit O (k) Speicher O (n) Zeit

11

Angenommen, wir lesen eine Folge von Zahlen nacheinander. So finden Sie das k -kleinste Element nur mit dem O ( k ) -Zellenspeicher und in linearer Zeit ( O ( n ) ). Ich denke, wir sollten die ersten k Terme der Sequenz speichern und, wenn wir den k + 1 -ten Term erhalten, einen Term löschen, von dem wir sicher sind, dass er nicht das k -kleinste Element sein kann, und dann den k + 1 -ten Term speichern . Wir sollten also einen Indikator haben, der diesen unbrauchbaren Begriff in jedem Schritt anzeigt, und dieser Indikator sollte in jedem Schritt schnell aktualisiert werden. Ich begann mit "max"nkO(k)O(n)kk+1kk+1;; Es kann jedoch nicht schnell aktualisiert werden. Bedeutet, wenn wir max berücksichtigen, dann verpassen wir beim ersten Löschen das Maximum und sollten in und seiner Ursache ( n - k ) × O ( k ) Zeit nach max suchen , damit es nicht linear ist. Vielleicht sollten wir die ersten k Terme der Sequenz intelligenter speichern .O(k)(nk)×O(k)k

Wie löse ich dieses Problem?

Shahab_HK
quelle
1
Interessieren Sie sich für einen Online-Algorithmus oder würde ein Algorithmus dies tun?
Yuval Filmus
Wenn ist, können Sie dies mithilfe des Ordnungsstatistikalgorithmus tun. Wenn k = o ( n ) ist, können Sie O ( k ) -Speicher und O ( n log k ) -Zeit unter Verwendung beliebiger Bäume mit ausgeglichener Höhe ausführen. k=θ(n)k=o(n)O(k)O(nlogk)
Shreesh
Es heißt das Auswahlproblem en.wikipedia.org/wiki/Selection_algorithm
xavierm02
Es gibt lineare Time-In-Place-Algorithmen, die Sie googeln können, die jedoch etwas kompliziert sind.
Yuval Filmus
@ xavierm02 es ist nicht das Auswahlproblem identisch. Weil es eine Speicherbeschränkung gibt.
Shahab_HK

Antworten:

16

Erstellen Sie einen Puffer der Größe . Lesen Sie 2 k Elemente aus dem Array ein. Verwenden Sie einen linearen Zeitauswahlalgorithmus, um den Puffer so zu partitionieren, dass die k kleinsten Elemente an erster Stelle stehen. Dies dauert O ( k ) Zeit. Lesen Sie nun weitere k Elemente aus Ihrem Array in den Puffer ein, ersetzen Sie die k größten Elemente im Puffer, partitionieren Sie den Puffer wie zuvor und wiederholen Sie den Vorgang.2k2kkO(k)kk

Dies dauert Zeit und O ( k ) Raum.O(kn/k)=O(n)O(k)

jbapple
quelle
+1, das passt zu den gestellten Asymptotikern. Abgesehen davon glaube ich nicht, dass dies schneller ist als ein einzelner Auswahlalgorithmus für die lineare Zeit ... außer wenn eine kleine Konstante ist, bietet es eine interessante Perspektive. Zum Beispiel für k = 1 erzeugt dieser Algorithmus die Funktion. kk=1min
Orlp
1
Manchmal verwendet der Algorithmus zur linearen Zeitauswahl zu viel Platz. Beispielsweise ist es nicht für die Verwendung in einem Streaming-Kontext oder wenn das Eingabearray unveränderlich ist, geeignet.
jbapple
Das sind gültige Punkte.
Orlp
3

Sie können dies im -Speicher und in der O ( n log k ) -Zeit tun, indem Sie aus den ersten k Elementen in der O ( k ) -Zeit einen Max-Heap mit fester Größe bilden , dann über den Rest des Arrays iterieren und einen neuen verschieben Element und dann Popping für O ( log k ) für jedes Element, was die Gesamtzeit O ( k + n log k ) = O ( n log k ) ergibt .O(k)O(nlogk)kO(k)O(logk)O(k+nlogk)O(nlogk)

Sie können dies im -Hilfsspeicher und in der O ( n ) -Zeit tun, indem Sie den Median-of-Medians-Auswahlalgorithmus verwenden, bei k auswählen und die ersten k Elemente zurückgeben. Ohne Änderung der Asymptotik können Sie Introselect verwenden, um den Durchschnittsfall zu beschleunigen. Dies ist der kanonische Weg, um Ihr Problem zu lösen.O(logn)O(n)kk

Technisch gesehen sind und O ( k ) unvergleichlich. Ich behaupte jedoch, dass O ( log n ) in der Praxis besser ist, da es effektiv konstant ist, wenn man bedenkt, dass kein Computersystem mehr als 2 64 Byte Speicher hat, log 2 64 = 64 . In der Zwischenzeit kann k so groß werden wie n .O(logn)O(k)O(logn)264log264=64kn

orlp
quelle
Beachten Sie, dass Sie die Komplexität des Heap-basierten Algorithmus auf verbessern können, indem Sie die vom Heap verwendete Reihenfolge umkehren, wenn dies interessant ist. O(n×logmin(k,nk))
Xavierm02
@ xavierm02 = O ( k ) . Beweis: Der schlechteste Fall für k ist n . Der schlechteste Fall für m i n ( k , n - k ) ist nO(min(k,nk))O(k)knmin(k,nk) . Sie sind innerhalb eines konstanten Faktors gleich, also ist O(min(k,n-k))=O(k). n2O(min(k,nk))O(k)
Orlp
@ xavierm02 Davon abgesehen ist es immer noch eine schöne Beschleunigung :)
Orlp
ist O ( k ), aber es ist nicht O ( min ( k , n - k ) ) . Angenommen, es ist. Dann gibt es etwas C und etwas M, so dasswirfür jedes M k n k C ( n - k ) haben , was eindeutig falsch ist (weil wir n = k + ∞ nehmen können ) .un,k=kO(k)O(min(k,nk))CMMknkC(nk)n=k+). Also ist . O(min(k,nk))O(k)
Xavierm02
@ xavierm02 Ich bin nicht vertraut mit Ihrer Notation. Um fair zu sein, bin ich mit der mehrdimensionalen Big- O- Notation im Allgemeinen nicht vertraut , insbesondere wenn man bedenkt, dass die Dimensionen n , k nicht unabhängig voneinander sind. un,kOn,k
Orlp