Temukan median daftar array yang diurutkan

8

Input: Satu set array (angka). Elemen-elemen dalam setiap array berada dalam urutan, tetapi set array tidak perlu diurutkan. Array tidak harus berukuran sama. Jumlah elemen adalah . $\ell$ $A_i$
$n$

Output: The $k$ th elemen terkecil dari semua elemen dalam input.

Apa algoritma yang paling efisien untuk masalah ini?

Apakah mungkin, misalnya untuk mencapai waktu berjalan $O(\ell + \log n)$ ?

algorithms algorithm-analysis Joe
sumber

Ada pertanyaan yang sangat erat terkait pada SO , dengan jawaban yang tidak memuaskan.

Joe

Apakah semua array memiliki panjang yang sama?

vonbrand

Array tidak harus berukuran sama. Namun, saya juga tertarik pada kasus khusus di mana ukurannya geometris, yaitu array

A_{i}

$A_i$ memiliki ukuran

n / 2^{i}

$n / 2^i$ , tapi saya ragu itu akan membantu dalam menjalankan waktu.

Joe

4

Bagaimana Anda mendapatkan ? Anda bisa mendapatkan dengan meniru algoritma "quickselect". Di setiap fase, Anda memilih pivot dan menghitung berapa banyak elemen di bawahnya, di . Kemudian Anda menghapus elemen di sisi yang salah, dan ulangi. Proses berakhir setelah iterasi (dalam harapan, atau dalam kasus terburuk jika Anda memilih pivot cerdas).

O (ℓ \log n)

$O(\ell\log n)$

O (ℓ (\log n)^{2})

$O(\ell(\log n)^2)$

O (ℓ \log n)

$O(\ell\log n)$

\log n

$\log n$

Yuval Filmus

2

@ Jo, saya pikir Anda harus menggambarkan algoritma Anda juga. Ini akan sangat menarik, dan dapat memberikan titik awal untuk algoritma yang lebih baik jika benar. Jika salah, orang mungkin dapat menemukan kesalahan.

Paresh

5

Anda dapat melakukannya dalam waktu dan ruang ekstra sebagai berikut: $O(l + k \text{ log } l)$ $O(l)$

Buat tumpukan biner dengan satu entri untuk setiap array. Kunci untuk entri adalah elemen terkecil dalam array . Ini membutuhkan waktu . $i$ $A_i$ $O(l)$
Pilih entri terkecil dari heap dan hapus (ambil ) waktu). Tambahkan entri itu kembali ke tumpukan menggunakan entri terkecil berikutnya dalam array yang relevan sebagai kuncinya (lagi waktu). $O(\text{log } l$ $O(\text{log } l)$
Lakukan langkah kali sebelumnya . Elemen terakhir yang Anda hapus dari tumpukan adalah jawaban Anda. $k$

Jika Anda mengganti tumpukan biner dengan tumpukan Fibonacci, saya pikir ini membuat Anda turun ke waktu diamortisasi , tetapi dalam praktiknya akan lebih lambat daripada tumpukan biner kecuali jika BESAR. $O(l + k)$ $l$

Saya menduga bahwa tumpukan Fibonacci terikat optimal, karena secara intuitif Anda akan harus memeriksa setidaknya elemen untuk menemukan th terkecil, dan Anda akan harus memeriksa setidaknya satu elemen dari masing-masing array karena Anda tidak tahu bagaimana mereka diurutkan, yang segera memberi batas bawah . $k$ $k$ $l$ $\Omega(\text{max}(k, l)) = \Omega(k + l)$

Matt Lewis
sumber

3

Anda tidak perlu memeriksa setidaknya elemen karena array diurutkan. Lihat solusi dalam komentar saya, yang memberikan .

k

$k$

O (ℓ (\log n)^{2})

$O(\ell (\log n)^2)$

Yuval Filmus

1

Anda dapat meningkatkan waktu berjalan terburuk dalam model RAM, karena Anda dapat menerapkan antrian prioritas Anda untuk elemen dalam . Dalam model ini, Anda dapat mencapai waktu untuk menyisipkan dan menghapus operasi dan untuk operasi findMin.

n

$n$

o (\log n)

$o(\log n)$

O (\sqrt{\log \log n})

$\mathcal{O}(\sqrt{\log \log n})$

O (1)

$\mathcal{O}(1)$

Massimo Cafaro

1

Apakah Anda yakin tumpukan Fibonnaci mendukung operasi yang benar? Saya pikir Anda berpikir tentang penurunan -kunci di min-heap.

Joe

Ini pada dasarnya sama dengan jawaban vonbrand, dengan pengamatan tambahan bahwa Anda tidak harus menggabungkan elemen apa pun setelah yang ke-k.

Joe

Saya percaya tumpukan Fibonacci memungkinkan Anda untuk mengurangi atau menambah kunci dalam waktu . Ya, ini pada dasarnya jawaban yang sama, tetapi mengamati bahwa Anda hanya perlu menggabungkan elemen membawa runtime Anda dengan cara yang adil.

O (1)

$O(1)$

k

$k$

Matt Lewis

5

Berikut adalah algoritma acak . Mungkin dapat derandomized menggunakan trik yang sama yang digunakan untuk derandomisasi quickselect yang biasa. $O(\ell\log^2 n)$

Kami meniru algoritma pemilihan cepat klasik. Di setiap fase, Anda memilih pivot dan menghitung berapa banyak elemen di bawahnya, di , menggunakan pencarian biner di setiap daftar. Kemudian Anda menghapus elemen di sisi yang salah, dan ulangi. Proses berakhir setelah iterasi dalam harapan $O(\ell\log n)$ $\log n$

Yuval Filmus
sumber

1

Hal ini tampaknya diselesaikan oleh makalah Generalized selection and ranking (Preliminary Version) oleh Frederickson dan Johnson dalam STOC '80.

Mereka memberikan batas atas dan bawah dari: yang ternyata menjadi untuk sebagian besar distribusi ukuran array. $\Theta(\ell + \sum_{i=1}^\ell \log|A_i|)$ $\ell \log n$

Algoritma aktual untuk mencapai batas atas rupanya diberikan dalam makalah sebelumnya: Algoritma optimal untuk menghasilkan informasi kuantil dalam X + Y dan matriks dengan kolom diurutkan , Proc. Konferensi Tahunan ke-13 tentang Ilmu dan Sistem Informasi, Universitas Johns Hopkins (1979) 47-52.

Joe
sumber

0

Sebuah -cara merge membutuhkan waktu (menggunakan cara yang efisien untuk mewakili antrian prioritas elemen kepala di setiap daftar), maka Anda memilih elemen -th dalam waktu yang konstan. Saya pikir ini dibahas dalam "Penyortiran dan pencarian" Knuth untuk menyortir. Mendapatkan yang terkecil (atau terbesar) jelas membutuhkan , untuk array yang tidak disortir adalah IIRC. $\ell$ $\Theta(n \log \ell)$ $k$ $\Theta(\ell)$ $O(n)$

Tolong jelaskan algoritma Anda.

vonbrand
sumber

1

Ini jauh lebih lambat daripada yang saya minati. Anda dapat menemukan median dalam waktu hanya menggabungkan daftar dan menggunakan algoritma pemilihan waktu linier.

O (n)

$O(n)$

Joe

Temukan median daftar array yang diurutkan

Jawaban: