Terikat pada ruang untuk algoritma seleksi?

Ada algoritma pemilihan kasus terburuk yang terkenal untuk menemukan elemen terbesar k dalam array bilangan bulat. Ia menggunakan pendekatan median-of-median untuk menemukan pivot yang cukup baik, mempartisi array input di tempat dan kemudian secara rekursif melanjutkan pencariannya untuk elemen terbesar k '.$O(n)$ $k$$k$

Bagaimana jika kita tidak diizinkan menyentuh array input, berapa banyak ruang tambahan yang dibutuhkan untuk menemukan elemen terbesar ke - dalam waktu O ( n ) ? Bisakah kita menemukan elemen terbesar k 'di O ( 1 ) ruang ekstra dan masih menjaga runtime O ( n ) ? Misalnya, menemukan elemen maksimum atau minimum membutuhkan O ( n ) waktu dan O ( 1 ) ruang. $k$$O(n)$$k$$O(1)$$O(n)$$O(n)$$O(1)$

Secara intuitif, saya tidak dapat membayangkan bahwa kita bisa melakukan yang lebih baik daripada ruang tetapi apakah ada buktinya?$O(n)$

Dapatkah seseorang menunjuk pada referensi atau mengemukakan argumen mengapa elemen 'memerlukan O ( n ) ruang untuk ditemukan dalam waktu O ( n ) ?$\lfloor n/2 \rfloor$$O(n)$$O(n)$

Ini adalah masalah terbuka jika Anda dapat melakukan seleksi dengan waktu dan O ( 1 ) sel memori tambahan tanpa mengubah input (lihat di sini ). Tapi Anda bisa mendekati ini.$O(n)$$O(1)$

$O(n^{1+\varepsilon})$$O(1/\varepsilon)$$\varepsilon>0$

$O(n)$$p$$p$

$p$$A(k)$$\varepsilon=1/k$$A(k)$$A(k-1)$$A(1)$algoritma. Ukuran blok yang tepat (dan melakukan perhitungan matematika) memberi Anda waktu dan ruang yang dibutuhkan seperti yang disebutkan di atas.

Btw, algoritma yang Anda cari, baru-baru ini dinamai algoritma constant-work-space .

Saya tidak mengetahui adanya batas bawah.