Znalezienie k-tego najmniejszego elementu z danej sekwencji tylko z czasem O (k) pamięci O (k)

Załóżmy, że odczytujemy ciąg $n$ liczb, jeden po drugim. Jak znaleźć $k$ najmniejszy element za pomocą pamięci komórkowej $O(k)$ oraz w czasie liniowym ( $O(n)$ ). Myślę, że powinniśmy zapisać pierwsze $k$ wyrażeń w sekwencji, a kiedy otrzymamy $k+1$ -ty termin, usuń go, który z pewnością nie może być $k$ -tym najmniejszym elementem, a następnie zapisz $k+1$ -ty termin. Powinniśmy więc mieć wskaźnik, który pokazuje ten bezużyteczny termin na każdym etapie, a wskaźnik ten powinien być aktualizowany na każdym kroku szybko. Zacząłem od „max”; ale nie można szybko zaktualizować; Oznacza to, że jeśli weźmiemy pod uwagę max, to przy pierwszym usuwaniu pomijamy maksimum i powinniśmy szukać maksimum w $O(k)$ i jego przyczynie $(n-k)\times O(k)$ czas, że nie jest on liniowy. Może powinniśmy bardziej inteligentnie zapisać pierwsze $k$ warunków sekwencji.

Jak rozwiązać ten problem?

data-structures search-algorithms quicksort

— Shahab_HK
źródło

Czy jesteś zainteresowany algorytmem online, czy zrobiłby to jakiś algorytm?

— Yuval Filmus

Jeśli

k = θ (n)

$k = \theta(n)$ , możesz to zrobić za pomocą algorytmu statystyki zamówień. Jeśli

k = o (n)

$k = o(n)$ , możesz to zrobić Pamięć

O (k)

$O(k)$ i czas

O (n \log k)

$O(n\log k)$ przy użyciu dowolnego drzewa o zrównoważonej wysokości.

— Shreesh

To się nazywa problem selekcji en.wikipedia.org/wiki/Selection_algorithm

— xavierm02

Istnieją algorytmy czasu lokalnego liniowe, które można wyszukiwać w Google, ale są one nieco skomplikowane.

— Yuval Filmus

@ xavierm02 to nie problem identyczny. Ponieważ istnieje ograniczenie limitu pamięci.

— Shahab_HK

Odpowiedzi:

Utwórz bufor o rozmiarze . Wczytaj elementów z tablicy. Użyj algorytmu wyboru czasu liniowego, aby podzielić bufor, tak aby najmniejszych elementów było pierwsze; zajmuje to czas . Teraz wczytaj kolejne elementów z tablicy do bufora, zastępując największych elementów w buforze, podziel bufor jak poprzednio i powtórz. $2k$ $2k$ $k$ $O(k)$ $k$ $k$

To zajmuje czas i przestrzeń. $O(k * n/k) = O(n)$ $O(k)$

— jbapple
źródło

+1, to pasuje do zadanych asymptotyków. To powiedziawszy, nie sądzę, że jest to szybsze niż wykonanie pojedynczego algorytmu selekcji w czasie liniowym ... z wyjątkiem sytuacji, gdy

jest małą stałą, zapewnia to interesującą perspektywę. Na przykład dla

ten algorytm tworzy funkcję.

k

$k$

k = 1

$k = 1$ min

— orlp

Czasami algorytm wyboru czasu liniowego zajmuje zbyt dużo miejsca. Na przykład nie nadaje się do użycia w kontekście przesyłania strumieniowego lub gdy tablica wejściowa jest niezmienna.

— jbapple

To są ważne punkty.

— orlp

$O(k)$ $O(n \log k)$ $k$ $O(k)$ $O(\log k)$ $O(k + n\log k)$ $O(n \log k)$

$O(\log n)$ $O(n)$ $k$ $k$

$O(\log n)$ $O(k)$ $O(\log n)$ $2^{64}$ $\log 2^{64}= 64$ $k$ $n$

— orlp
źródło

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

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

@ xavierm02 = . Dowód: najgorszym przypadkiem dla jest . Najgorszy przypadek dla to . Są takie same w ramach stałego współczynnika, a zatem = .

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)$

\frac{n}{2}

$n \over 2$

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

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

O (k)

$O(k)$

— orlp

@ xavierm02 To powiedziawszy, to wciąż niezłe przyspieszenie :)

— orlp

u_{n, k} = k

$u_{n,k}=k$ to ale to nie . Załóżmy, że tak. Potem jest trochę i trochę tak że dla każdego mamy , co jest wyraźnie fałszywe (ponieważ możemy przyjąć Więc .

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).$

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

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

— xavierm02

@ xavierm02 Nie znam twojej notacji . Aby być uczciwym, ogólnie nie jestem zaznajomiony z wielowymiarową notacją big- , szczególnie biorąc pod uwagę, że wymiary nie są ze sobą niezwiązane.

u_{n, k}

$u_{n, k}$

O

$O$

n, k

$n, k$

— orlp