Jumlah perbandingan yang tepat untuk menghitung median

Volume III dari Knuth The Art of Computer Programming (pasal 5 ayat 3,2) termasuk mengikuti tabel daftar tepat jumlah minimum perbandingan yang diperlukan untuk memilih elemen th terkecil dari set disortir ukuran , untuk semua . Tabel ini, bersama dengan ekspresi bentuk tertutup terkenal dan , mewakili sebagian besar keadaan seni pada tahun 1976 . $t$ $n$ $1\le t \le n\le 10$ $V_1(n) = n-1$ $V_2(n) = n - 2 + \lceil n/2 \rceil$

Tabel dari Knuth III: 5.3.2

Apakah ada nilai yang lebih tepat dari dihitung dalam 36 tahun terakhir? Saya sangat tertarik pada nilai , jumlah minimum perbandingan yang diperlukan untuk menghitung median. $V_t(n)$ $M(n) = V_{\lceil n/2 \rceil}(n)$

Seperti yang ditunjukkan oleh @ MarkusBläser, tabel Knuth tampaknya sudah memasukkan hasil yang lebih baru dari Bill Gasarch, Wayne Kelly, dan Bill Pugh ( Menemukan engan terbesar n untuk n kecil, n . SIGACT News 27 (2): 88-96, 1996 .)

ds.algorithms reference-request co.combinatorics sorting selection Jeffε
sumber

Makalah yang paling terkenal tentang topik ini, saya pikir, adalah tentang Pratt dan Yao (1976) yang dianggap sebagai orang pertama yang menemukan beberapa teknik (permusuhan) untuk membuktikan kelemahan pada masalah ini. Jika saya menemukan makalah terbaru tentang masalah ini, saya akan mengikuti kutipan yang dibuat untuk makalah ini . Makalah terbaru adalah karya Dor dan Zwick, tetapi ada juga survei tahun 1996 oleh Paterson (meskipun saya belum melihat untuk melihat apakah itu menyangkut dirinya sendiri dengan hasil yang tepat atau tidak).

Jérémie

Nitpicking: Dalam kalimat terakhir dalam pertanyaan, Anda mungkin memaksudkan langit-langit daripada lantai.

Tsuyoshi Ito

Jeff, ingin tahu mengapa Anda tertarik pada jawaban yang tepat.

Chandra Chekuri

Kenneth Oksanen menulis kode yang efisien untuk komputasi . Sayangnya, hanya ada abstrak yang tersedia sciencedirect.com/science/article/pii/S1571065306001582 Dua tahun lalu, salah satu siswa saya mengiriminya email dan mendapat kode darinya. Saya tidak ingat apakah beberapa nilai baru dapat diperoleh.

V_{i} (n)

$V_i(n)$

Markus Bläser

@ChandraChekuri: Saya bermain-main dengan varian algoritma seleksi linear waktu Blum-Floyd-Pratt-Rivest-Tarjan , sebagai masalah potensial algoritma pekerjaan rumah. Jika kita menggunakan algoritma perbandingan minimum untuk menemukan median di setiap blok, lalu ukuran blok apa yang memberi kita konstanta terbaik di big-Oh? 9 lebih baik dari 7 lebih baik dari 5; bagaimana dengan 11?

Jeffε

Jawaban:

Kenneth Oksanen telah menerbitkan tabel nilai yang diperluas hingga , berdasarkan pencarian komputernya sendiri . Okansen juga memberikan deskripsi pohon perbandingan optimal untuk sebagian besar nilai yang ia laporkan. Berikut screenshot dari mejanya: $n=15$

Batas Kenneth Oksanen untuk seleksi

Terima kasih kepada @ MarkusBläser untuk petunjuknya!

Jeffε
sumber

Saya ingin tahu apakah informasi ini mungkin berguna bagi Anda. Sayangnya itu tidak memberikan informasi tambahan untuk pertanyaan posting ini, tetapi lebih merupakan balasan untuk komentar Anda tentang apa ini untuk (menganalisis varian QuickSelect).

Jumlah perbandingan minimum yang diharapkan, yang dicatat atau tentu saja secara signifikan lebih mudah untuk dihitung (dengan harapan diambil secara seragam atas semua permutasi), $v(n,t)$ $v_t(n)$

v_{t} (n) = n + min (t, n - t) + l.o.t. .

$v_t(n)=n+\min(t,n-t)+\text{l.o.t.}.$

Hasil ini tidak jarang digunakan, dan khususnya adalah dasar untuk algoritma dalam "Adaptive Sampling for QuickSelect" oleh Martínez, Panario dan Viola . Titik awal dari makalah ini adalah QuickSelect median-of-three, dan kemudian bertanya: apakah berkaitan dengan memilih median secara sistematis, ketika elemen yang kita cari memiliki peringkat relatif jauh lebih rendah dari n / 2 atau lebih tinggi dari n / 2 ?

Dengan kata lain, misalkan Anda mencari elemen -th dalam daftar elemen, dan Anda memilih poros Anda dari kelompok elemen . Alih-alih mengambil median ( ), Anda akan mengambil mana . Mereka menunjukkan algoritma ini dapat, untuk pilihan secara praktis lebih efisien daripada varian median-of-three. $k$ $n$ $m$ $m/2$ $\alpha m$ $\alpha = k/n$ $m$

Jérémie
sumber