Apa cara tercepat untuk menemukan nilai terkecil Kth dalam daftar yang tidak disortir tanpa pengurutan?

8

Algoritme awal saya:

  1. Bandingkan elemen 0 dengan setiap elemen lainnya, catat berapa banyak elemen yang kurang dari itu.
  2. Ulangi untuk setiap elemen sampai elemen yang lebih besar dari elemen (k-1) ditemukan.

Saya menganggap ini akan mengambil dalam kasus terburuk. Bisakah runtime lebih cepat dicapai tanpa mengurutkan daftar?O(n2)

search-algorithms lists MENGAPA
sumber
9
Kemungkinan rangkap dari Menemukan elemen terkecil dari urutan yang diberikan hanya dengan memori O (k) O (n) waktu
user2357112 mendukung Monica
Bisakah Anda membuat daftar kedua, dan mengurutkannya? Yaitu Bisakah Anda membuat daftar nilai k terkecil?
jmoreno

Jawaban:

10

Gunakan algoritma pemilihan untuk waktu linier https://en.m.wikipedia.org/wiki/Selection_algorithm

Eugene
sumber
2
Khususnya Median of Medians oleh Blum et al., 1973, memecahkan masalah seleksi dalam waktu linear terburuk. Mungkin algoritma paling elegan yang pernah saya lihat.
quicksort
6
Meskipun ini menjawab pertanyaan, disarankan untuk membuat deskripsi sendiri, bukan hanya tautan.
Jahat
4

Sayangnya saya tidak bisa hanya berkomentar tetapi saya harus mempostingnya sebagai jawaban.

Bagaimanapun, Anda bisa mencoba menggunakan min-heap pada array yang tidak disortir, Anda harus bisa mendapatkan kompleksitas waktu O (n + k * logn).

Luca Giorgi
sumber
3
Sayangnya saya tidak bisa hanya berkomentar tetapi saya harus mempostingnya sebagai jawaban. - yang merupakan hal yang baik, karena jawaban seperti kiriman Anda tidak termasuk dalam komentar. Komentar adalah untuk memperbaiki pertanyaan, bukan untuk jawaban pendek atau serupa.
Wrzlprmft
1
Mh, saya merasa seperti milik saya bukan jawaban yang lengkap untuk jujur, saya belum memberikan spesifik tentang mengapa atau bagaimana penggunaan tumpukan min bisa menurunkan kompleksitas waktu, itu sebabnya saya merasa seperti itu milik lebih banyak di komentar daripada di jawaban
Luca Giorgi
Tergantung pada apakah min-heap atau max-heap harus digunakan. k
Jahat
3

Algoritma Quickselect dapat melakukan itu dalam kompleksitas rata-rata O (n), ini adalah salah satu algoritma seleksi yang paling sering digunakan menurut Wikipedia .

Ini berasal dari QuickSort dan karena itu menderita kompleksitas kasus terburuk O (n²) jika Anda menggunakan pivot yang buruk (masalah yang dapat dihindari dalam praktiknya).

Algoritma singkatnya: Setelah pivoting seperti di QuickSort, hanya turun ke sisi yang lebih rendah atau lebih tinggi dari array - tergantung di mana mereka memiliki elemen yang Anda cari.

Nestor Demeure
sumber
2

Buat tumpukan maksimum ukuran . Invarian adalah bahwa tumpukan selalu berisi elemen terkecil diamati sejauh ini.kk

  1. Masukkan elemen pertama dari daftar ke heapk
  2. Untuk setiap elemen yang tersisa, dalam daftar: i
    • biarkan menjadi elemen maksimum di heapM
    • Jika , maka hapus dan masukkan ke heapi<MMi

Pada akhirnya, heap akan mengandung elemen terkecil dalam daftar.k

Mencari elemen maksimum memiliki biaya konstan. Biaya penyisipan dan penghapusan adalah . Kompleksitas waktu dari metode ini adalahO(k)O(n.log⁡k)

Behrouz Babaki
sumber
1
Max-heap atau Min-heap, itu tergantung pada k> n / 2.
Jahat
@ Evil Anda ingin memeriksa apakah saya lebih kecil dari elemen apa pun di heap. Jadi, Anda ingin tahu apakah itu lebih kecil dari yang terbesar. Mencari elemen maksimum adalah O (1) di max-heap, tetapi tidak di min-heap.
Behrouz Babaki
1
Benar. Bayangkan k = 1 atau k = n, apakah Anda akan menggunakan tumpukan yang sama dalam kedua kasus? Mungkin dimungkinkan untuk menggunakan min-heap entah bagaimana ketika lebih cepat? (Saya tahu itu, Anda punya +1 dari saya, hanya nitpick, jangan khawatir).
Jahat
1
@ Evil Anda benar. Saya membuang komentar Anda dengan tergesa-gesa. Ketika k> n / 2, seseorang dapat menggunakan metode serupa untuk menyimpan elemen (nk) terbesar di tumpukan-min. Elemen yang dihapus dari tumpukan adalah apa yang kita inginkan.
Behrouz Babaki