Pilih dalam gabungan array yang disortir: Sudah dikenal?

Saya mencari referensi bibliografi untuk algoritme / masalah berikut: Saya menamakannya "BiSelect" atau "t-ary Select" atau "Select in Union of Sorted Arays", tapi saya kira itu diperkenalkan sebelum dengan nama lain?

Masalah

Pertimbangkan masalah berikut:

Mengingat $k$ disjoint array yang disortir $A_1,\ldots, A_k$ , dengan ukuran masing-masing $n_1,\ldots,n_k$ , dan integer $t\in[1..\sum n_i]$ , berapakah nilai $t$ -th dari serikat yang disortir $\cup_i A_i$ ?

Solusi

$O(\lg\min\{n_1,n_2,t\})$k = 2 A 1 [ t / 2 ] A 2 [ t / 2 ] A 1 [ t / 2 .. t ] A 2 [ 1 .. t / 2 ] A 1 [ 1 .. t / 2 ] A 2 [ t / 2 .. t ] t / 2 n 1 n 2$k=2$$k=2$$A_1[t/2]$$A_2[t/2]$$A_1[t/2..t]$$A_2[1..t/2]$$A_1[1..t/2]$$A_2[t/2..t]$$t/2$$n_1$$n_2$$t$

Ini digeneralisasikan ke algoritma yang sedikit lebih canggih yang berjalan dalam waktu $O(k\lg t)$ untuk nilai k yang lebih besar $k$, berdasarkan pada penghitungan median nilai-nilai $A_i[t/k]$ untuk $i\in[1..k]$ : the $t/k$ elemen terkecil dapat lebih lanjut diabaikan dalam array $k/2$ mana $A_i[t/k]$ lebih kecil dari median, dan elemen peringkat di $[t-t/k..]$ dapat lebih lanjut diabaikan dalam $k/2$ array lainnya, menghasilkan separuh dari $t$ dalam setiap pengulangan (dan biaya $O(k)$ untuk median).

Referensi?

Saya senang dengan solusi saya, tetapi saya kira masalahnya (dan solusinya) sudah diketahui. Hal ini terkait dengan algoritma waktu linier untuk menghitung median (dengan menyortir kelompok ukuran , dan muncul kembali pada median middle mereka), tetapi sedikit lebih umum. Saya bertanya kepada beberapa perguruan tinggi di Madalgo di Aarhus (Denmark), dan kemudian beberapa lainnya di bengkel Stringology (Rouen), tanpa hasil: Saya berharap seseorang yang lebih berpengetahuan dapat membantu di Stack Exchange ...$5$

Motivasi

Solusi untuk masalah ini memiliki aplikasi untuk Struktur Data yang Ditangguhkan pada array (memang, dapat dilihat sebagai operator dalam struktur data yang ditangguhkan untuk penyatuan array yang diurutkan); dan dengan cara yang lebih berbelit-belit, dengan perhitungan adaptif kode bebas awalan yang optimal.

Algoritma yang dijelaskan oleh Frederickson dan Johnson pada tahun 1982 menganggap bahwa semua set memiliki ukuran yang sama. Mereka juga menggambarkan pada tahun 1980 solusi optimal yang mengambil keuntungan dari berbagai ukuran set yang diurutkan. Kompleksitas dari algoritma ini adalah dalam .$O(k + \sum^k_{i=1}\log{n_i})$

Referensi

Greg N. Frederickson dan Donald B. Johnson. 1980. Seleksi dan peringkat umum (Versi Pendahuluan). Dalam Prosiding simposium ACM tahunan kedua belas tentang Teori komputasi (STOC '80). ACM, New York, NY, AS, 420-428. DOI = 10.1145 / 800141.804690 http://doi.acm.org/10.1145/800141.804690

Frederickson dan Johnson memperoleh hasil optimal di tahun 80-an. Misalkan , lalu ada algoritma yang memecahkan masalah Anda di .O ( k + p log $p=\min(k,t)$$O(k+p \log \frac{t}{p})$

Referensi

GN Frederickson, DB Johnson " Kompleksitas seleksi dan peringkat dalam x + y dan matriks dengan kolom diurutkan " J. Comput. System Sci., 24 (2) (1982), hlm. 197–208

Kasing k = 2 muncul dalam sortir gabungan paralel karena penggabungan dua susunan yang diurutkan dari utas yang berbeda perlu dipisah di antara dua utas untuk mempertahankan jumlah paralelisme yang sama. Solusi pekerjaan rumah ini adalah salah satu referensi.