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

Angenommen, wir lesen eine Folge von Zahlen nacheinander. So finden Sie das -kleinste Element nur mit dem -Zellenspeicher und in linearer Zeit ( ). Ich denke, wir sollten die ersten Terme der Sequenz speichern und, wenn wir den -ten Term erhalten, einen Term löschen, von dem wir sicher sind, dass er nicht das -kleinste Element sein kann, und dann den -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" $n$ $k$ $O(k)$ $O(n)$ $k$ $k+1$ $k$ $k+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 Zeit nach max suchen , damit es nicht linear ist. Vielleicht sollten wir die ersten Terme der Sequenz intelligenter speichern . $O(k)$ $(n-k)\times O(k)$ $k$

Wie löse ich dieses Problem?

data-structures search-algorithms quicksort Shahab_HK
quelle

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

ist, können Sie

-Speicher und

-Zeit unter Verwendung beliebiger Bäume mit ausgeglichener Höhe ausführen.

k = θ (n)

$k = \theta(n)$

k = o (n)

$k = o(n)$

O (k)

$O(k)$

O (n \log k)

$O(n\log k)$

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:

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

Dies dauert Zeit und Raum. $O(k * n/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

erzeugt dieser Algorithmus die Funktion.

k

$k$

k = 1

$k = 1$ min

Orlp

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

Sie können dies im -Speicher und in der tun, indem Sie aus den ersten Elementen in der -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 für jedes Element, was die Gesamtzeit = ergibt . $O(k)$ $O(n \log k)$ $k$ $O(k)$ $O(\log k)$ $O(k + n\log k)$ $O(n \log k)$

Sie können dies im -Hilfsspeicher und in der -Zeit tun, indem Sie den Median-of-Medians-Auswahlalgorithmus verwenden, bei auswählen und die ersten 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(\log n)$ $O(n)$ $k$ $k$

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

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 \times \log min (k, n - k))

$O(n \times \log\min (k, n - k))$

Xavierm02

@ xavierm02

. Beweis: Der schlechteste Fall für

ist

. Der schlechteste Fall für

ist

O (m i n (k, n - k))

$O(min(k, n-k))$

O (k)

$O(k)$

k

$k$

n

$n$

m i n (k, n - k)

$min(k, n-k)$

. Sie sind innerhalb eines konstanten Faktors gleich, also ist

\frac{n}{2}

$n \over 2$

O (m i n (k, n - k))

$O(min(k, n-k))$

O (k)

$O(k)$

Orlp

@ xavierm02 Davon abgesehen ist es immer noch eine schöne Beschleunigung :)

Orlp

ist

aber es ist nicht

. Angenommen, es ist. Dann gibt es etwas

und etwas

so dasswirfür jedes

, was eindeutig falsch ist (weil wir

u_{n, k} = k

$u_{n,k}=k$

O (k)

$O(k)$

O (min (k, n - k))

$O(\min (k, n-k))$

C

$C$

M

$M$

M \leq k \leq n

$M\le k\le n$

k \leq C (n - k)

$k\le C (n-k)$

n = k \to + \infty) .

$n=k \to +\infty).$ Also ist

O (min (k, n - k)) ⊊ O (k)

$O(\min(k, n-k))\subsetneq O(k)$

Xavierm02

@ xavierm02 Ich bin nicht vertraut mit Ihrer

Notation. Um fair zu sein, bin ich mit der mehrdimensionalen Big-

Notation im Allgemeinen nicht vertraut , insbesondere wenn man bedenkt, dass die Dimensionen

nicht unabhängig voneinander sind.

u_{n, k}

$u_{n, k}$

O

$O$

n, k

$n, k$

Orlp