znajdowanie najmniejszych k elementów w tablicy w O (k)

12

To interesujące pytanie znalazłem w Internecie. Biorąc pod uwagę tablicę zawierającą n liczb (bez informacji o nich), powinniśmy wstępnie przetworzyć tablicę w czasie liniowym, abyśmy mogli zwrócić k najmniejszych elementów w czasie O (k), gdy otrzymamy liczbę 1 <= k <= n

Dyskutowałem o tym problemie z przyjaciółmi, ale nikt nie mógł znaleźć rozwiązania; każda pomoc będzie mile widziana!

krótkie uwagi: - kolejność k najmniejszych elementów nie jest ważna - elementy w tablicy są liczbą, mogą być liczbami całkowitymi i mogą nie być (więc brak sortowania w radix) - liczba k nie jest znana na etapie wstępnego przetwarzania. przetwarzanie wstępne to czas O (n). funkcja (znajdź k najmniejszych elementów) w czasie O (k).

sorting

— Idan
źródło

4

Co powiesz na korzystanie z min-sterty?

— Shir

1

Spójrz na obliczenia k-skyband i top-k. Artykuł cs.sfu.ca/~jpei/publications/subsky_tkde07.pdf ma niezły przegląd powiązanej literatury.

— András Salamon

1

Shir-ja zbadałem pomysł na min-stos. jednak w celu wydrukowania k najmniejszych liczb na stercie min jest czas O (klogn), a nie O (k) zgodnie z wymaganiami

— Idan

4

@idannik: Jak myślisz, dlaczego potrzeba

aby znaleźć

najmniejszych elementów na min-stercie?

Ω (k \log n)

$\Omega(k \log n)$

k

$k$

— Kristoffer Arnsfelt Hansen

8

Nie sądzę, żeby to był poziom badań. Wygląda jak zadanie. Gdzie to znalazłeś?

— Kaveh

24

Przetwórz wstępnie tablicę wartości w czasie : $n$ $O(n)$

$i\leftarrow n$
podczas gdy
- Obliczyć średnią o w czasie $m$ $A[1..i]$ $O(i)$
- Partycja w i w tym samym czasie. $A[1..i]$ $A[1..i/2-1] \leq m$ $A[i/2+1..i]\geq m$
- $i \leftarrow \lfloor i/2 \rfloor$

Całkowity czas precomputation jest w $O(1+2+4+...+n)\subseteq O(n)$

Odpowiedz na zapytanie o najmniejszych elementów w w czasie : $k$ $A$ $O(k)$

$l\leftarrow \lfloor \log_2 k \rfloor$
wybierz th element z w czasie $(k-2^l)$ $x$ $A[2^l..2^{l+1}]$ $O(2^l)\subseteq O(k)$
przegroda przez w tym samym czasie $A[2^l..2^{l+1}]$ $x$

zawiera najmniejszych elementów. $A[1..k]$ $k$

Bibliografia:

W 1999 roku Dor i Zwick podali algorytm obliczający medianę elementów w czasie w ramach porównań , co daje algorytm do wyboru tego elementu spośród nieuporządkowanych elementów w mniej niż porównaniach. $n$ $2.942 n + o(n)$ $k$ $n$ $6n$

— Jeremy
źródło

1

mi się, że zewnętrzna pętla powinna być „dla i w

”. Czy twój algorytm różni się od algorytmu zawartego w odpowiedzi Yuval Filmus?

{2^{⌈ \lg n ⌉}, \dots, 4, 2, 1}

$\{2^{\lceil\lg n\rceil},\dots,4,2,1\}$

— Radu GRIGore

2

To jest uogólnienie mojego algorytmu na dowolny

. Zawiera również niektóre szczegóły implementacji, które (celowo) zostały pominięte w mojej odpowiedzi.

n

$n$

— Yuval Filmus

3

@YuvalFilmus Czy w swoim komentarzu chcesz zasugerować, że moja odpowiedź jest nieetycznie zbliżona do twojej? Jest to rozwiązanie, które przyszło mi do głowy, kiedy przejrzałem pytanie. Widziałem, że opublikowałeś podobny, ale okazało się, że jest niejasny, więc napisałem własny (w przeciwieństwie do robienia poważnych zmian). Ostatecznie liczy się jakość odpowiedzi w systemach, a nie to, kto je napisał: odznaki i reputacja to tylko zachęty, a nie same w sobie cele.

— Jeremy

4

n

$n$

2

Och :( W takim razie przepraszam za to. (Chociaż nadal uważałbym, że udzielenie kompletnych odpowiedzi jest priorytetem w stosunku do podejrzeń o przydzielenie zadania)

— Jeremy

14

$n = 2^m$ $2^{m-1},2^{m-2},2^{m-3},\ldots,1$ $k$ $t$ $2^{t-1} \leq k \leq 2^t$ $2^t \leq 2k$ $2^t$ $k$ $O(2^t) = O(k)$

$\Theta(n\log n)$

while n > 0:
  find the (lower) median m of A[0..n-1]
  partition A in-place so that A[n/2-1] = m
  n = n/2

$n + n/2 + n/4 + \cdots + 1 < 2n$ $A$ $k$ $A[0..n/2^k-1]$ $n/2^k$

— Yuval Filmus
źródło

1

O (1)

$O(1)$

k

$k$

O (n)

$O(n)$

4

\log n

$\log n$

n \log n

$n \log n$

3

@ AndrásSalamon: Jeśli przeczytasz odpowiedź udzieloną przez Jeremy'ego (która wygląda mi prawie tak samo jak ta), zobaczysz, że najpierw przetwarzasz całą tablicę, potem pierwszą połowę i tak dalej.

— Radu GRIGore

3

n + n / 2 + n / 4 + \dots + 1 < 2 n

$n+n/2+n/4+\cdots+1 < 2n$

5

Nawiasem mówiąc, ten algorytm pojawia się jako podprogram w mojej odpowiedzi na wcześniejsze pytanie: cstheory.stackexchange.com/questions/17378/…

— David Eppstein

2

$O(n)$ $O(k)$ $k$

Frederickson, Greg N. , Optymalny algorytm do selekcji w hałdzie min. , Inf. Comput. 104, nr 2, 197–214 (1993). ZBL0818.68065 ..

— hqztrue
źródło

1

k

$k$

O (k)

$O(k)$

@ a3nm To rzeczywiście nie jest prosty algorytm, ale zaktualizowałem referencję.

— hqztrue

k

$k$

k

$k$

O (k)

$O(k)$

k

$k$

k

$k$

x

$x$

< x

$<x$

O (k)

$O(k)$

k

$k$

k / 2

$k/2$

k

$k$

0

$k$ $k$

— jbapple
źródło

1

k

$k$

2

Widzę. Mój błąd.

— jbapple

znajdowanie najmniejszych k elementów w tablicy w O (k)

Przetwórz wstępnie tablicę wartości w czasie O ( n ) :nnnO ( n )O(n)O(n)

Odpowiedz na zapytanie o najmniejszych elementów w A w czasie O ( k ) :kkkAAAO(k)O(k)O(k)

Bibliografia:

Przetwórz wstępnie tablicę wartości w czasie : $n$ $O(n)$

Odpowiedz na zapytanie o najmniejszych elementów w w czasie : $k$ $A$ $O(k)$