menemukan elemen k terkecil dalam array di O (k)

12

Ini adalah pertanyaan menarik yang saya temukan di web. Diberikan array yang berisi n angka (tanpa informasi tentangnya), kita harus memroses terlebih dahulu array dalam waktu linier sehingga kita dapat mengembalikan elemen terkecil k dalam waktu O (k), ketika kita diberi angka 1 <= k <= n

Saya telah membahas masalah ini dengan beberapa teman tetapi tidak ada yang bisa menemukan solusi; bantuan apa pun akan dihargai!

catatan cepat: -rangka k elemen terkecil tidak penting-elemen dalam array adalah angka, mungkin bilangan bulat dan mungkin bukan (jadi tidak ada jenis radix) -jumlah k yang tidak diketahui pada tahap pra-pemrosesan. preprocessing adalah O (n) waktu. fungsi (temukan k elemen terkecil) pada waktu O (k).

sorting Idan
sumber

4

Bagaimana kalau menggunakan min-heap?

Shir

1

Lihatlah perhitungan k-skyband dan top-k. Makalah cs.sfu.ca/~jpei/publications/subsky_tkde07.pdf memiliki ulasan yang bagus tentang literatur terkait.

András Salamon

1

Shir-Saya telah memeriksa ide tumpukan-min. namun, untuk mencetak k angka terkecil dalam min heap adalah dalam waktu O (klogn) dan bukan O (k) seperti yang dipersyaratkan

Idan

4

@ idannik: Menurut Anda mengapa diperlukan

waktu untuk menemukan

elemen terkecil dalam min-heap?

Ω (k \log n)

$\Omega(k \log n)$

k

$k$

Kristoffer Arnsfelt Hansen

8

Saya tidak berpikir ini level penelitian. Sepertinya tugas. Di mana Anda menemukannya?

Kaveh

24

Memproses ulang array nilai dalam waktu : $n$ $O(n)$

$i\leftarrow n$
sementara
- Hitung median dari dalam waktu $m$ $A[1..i]$ $O(i)$
- partisi menjadi dan dalam waktu yang bersamaan. $A[1..i]$ $A[1..i/2-1] \leq m$ $A[i/2+1..i]\geq m$
- $i \leftarrow \lfloor i/2 \rfloor$

Total waktu precomputation adalah dalam $O(1+2+4+...+n)\subseteq O(n)$

Jawab pertanyaan untuk elemen terkecil di dalam waktu : $k$ $A$ $O(k)$

$l\leftarrow \lfloor \log_2 k \rfloor$
pilih elemen dari dalam waktu $(k-2^l)$ $x$ $A[2^l..2^{l+1}]$ $O(2^l)\subseteq O(k)$
partisi oleh dalam waktu yang bersamaan $A[2^l..2^{l+1}]$ $x$

berisielemen terkecil . $A[1..k]$ $k$

Referensi:

Pada tahun 1999, Dor dan Zwick memberikan algoritma untuk menghitung median elemen dalam waktu perbandingan, yang menghasilkan algoritma untuk memilih elemen ke- dari elemen tidak berurutan dalam perbandingan kurang dari . $n$ $2.942 n + o(n)$ $k$ $n$ $6n$

Jeremy
sumber

1

Saya kira lingkaran luar seharusnya 'untuk saya di

'. Apakah algoritma Anda berbeda dari yang ada di jawaban Yuval Filmus?

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

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

Radu GRIGore

2

Ini adalah generalisasi dari algoritma saya ke

sembarang . Itu juga menjabarkan beberapa detail implementasi yang (sengaja) ditinggalkan dari jawaban saya.

n

$n$

Yuval Filmus

3

@YuvalFilmus Anda ingin menyiratkan dengan komentar Anda bahwa jawaban saya tidak etis dekat dengan Anda? Ini adalah solusi yang muncul di benak saya ketika saya mengulas pertanyaan itu. Saya melihat bahwa Anda memposting yang serupa, tetapi ternyata tidak jelas, jadi saya menulis sendiri (sebagai lawan melakukan edit besar dari Anda). Yang penting pada akhirnya adalah kualitas jawaban pada sistem, bukan siapa yang menulisnya: lencana dan reputasi hanyalah insentif, bukan tujuan dalam diri mereka sendiri.

Jeremy

4

n

$n$

2

Oh :( Maaf soal itu. (Meskipun saya masih akan berpikir memberikan jawaban lengkap menjadi prioritas di atas kecurigaan penugasan)

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
sumber

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: Jika Anda membaca jawaban yang diberikan oleh Jeremy (yang terlihat bagi saya hampir sama dengan yang ini) Anda melihat bahwa Anda pertama kali memproses seluruh array, lalu bagian pertama, dan seterusnya.

Radu GRIGore

3

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

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

5

Kebetulan algoritma ini muncul sebagai subrutin dalam jawaban saya untuk pertanyaan sebelumnya: cstheory.stackexchange.com/questions/17378/…

David Eppstein

2

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

Frederickson, Greg N. , Algoritma yang optimal untuk seleksi dalam min-heap , Inf. Komputasi. 104, No. 2, 197-214 (1993). ZBL0818.68065 ..

hqztrue
sumber

1

k

$k$

O (k)

$O(k)$

@ a3nm Memang bukan algoritma yang sederhana, tapi saya sudah memperbarui referensi.

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
sumber

1

k

$k$

2

Saya melihat. Kesalahanku.

jbapple

menemukan elemen k terkecil dalam array di O (k)

Jawaban:

Memproses ulang array nilai dalam waktu O ( n ) :nnnO ( n )O(n)O(n)

Jawab pertanyaan untuk elemen terkecil di A dalam waktu O ( k ) :kkkAAAO(k)O(k)O(k)

Referensi:

Memproses ulang array nilai dalam waktu : $n$ $O(n)$

Jawab pertanyaan untuk elemen terkecil di dalam waktu : $k$ $A$ $O(k)$