Seleksi Acak

Algoritma pemilihan acak adalah sebagai berikut:

Input: Array dari angka (berbeda, untuk kesederhanaan) dan angkan k ∈ [ n $A$$n$$k\in [n]$

Output: The " elemen peringkat " dari A (yaitu, yang ada di posisi k jika A diurutkan)$k$$A$$k$$A$

Metode:

• Jika ada satu elemen dalam , kembalikan$A$
• Pilih elemen ("pivot") secara seragam secara acak$p$
• Hitung set dan R = { a ∈ A : a > p $L = \{a\in A : a < p\}$$R = \{a\in A : a > p\}$
• Jika , kembali peringkat k unsur L .$|L| \ge k$$k$$L$
• Jika tidak, kembalikan peringkat elemen $k - |L|$$R$

Saya ditanya pertanyaan berikut:

Misalkan , sehingga Anda mencari median, dan biarkan a ∈ ( 1 / 2 , 1 ) menjadi konstan. Berapa probabilitas bahwa, pada panggilan rekursif pertama, set yang berisi median memiliki ukuran paling banyak α n ?$k=n/2$$\alpha\in (1/2,1)$$\alpha n$

Saya diberitahu bahwa jawabannya adalah , dengan justifikasi "Pivot yang dipilih harus berada di antara 1 - α dan α kali array asli"$2\alpha - 1$$1−\alpha$$\alpha$

Mengapa? Sebagai , elemen apa pun yang dipilih sebagai pivot lebih besar atau lebih kecil dari lebih dari setengah elemen asli. Median selalu terletak pada subarray yang lebih besar, karena elemen-elemen dalam subarray yang dipartisi selalu kurang dari pivot.$\alpha \in (0.5, 1)$

Jika pivot terletak di paruh pertama array asli (kurang dari setengahnya), median pasti akan berada di setengah lebih besar kedua, karena begitu median ditemukan, ia harus berada di posisi tengah array, dan semuanya sebelum pivot lebih kecil seperti yang disebutkan di atas.

Jika pivot terletak di paruh kedua array asli (lebih dari setengah elemen), median pertama pasti akan lebih besar setengahnya, untuk alasan yang sama, segala sesuatu sebelum pivot dianggap lebih kecil.

Contoh:

3 4 5 8 7 9 2 1 6 10

Median adalah 5.

Misalkan pivot yang dipilih adalah 2. Jadi setelah iterasi pertama, itu menjadi:

1 2 .... bagian yang lebih besar ....

Hanya 1dan 2ditukar setelah iterasi pertama. Nomor 5 (median) masih di babak pertama yang lebih besar (menurut pivot 2). Intinya adalah, median selalu terletak pada setengah yang lebih besar, bagaimana ia dapat memiliki kesempatan untuk tinggal di subarray yang lebih kecil?

Misalkan array Anda memiliki elemen. Seperti yang telah Anda catat, median selalu berada di bagian yang lebih besar setelah partisi pertama. Bagian yang lebih besar memiliki ukuran paling banyak α n jika bagian yang lebih kecil memiliki ukuran setidaknya ( 1 - α ) n . Ini terjadi ketika Anda memilih pivot yang bukan salah satu dari elemen terkecil atau terbesar ( 1 - α ) n . Karena α > 1 / 2 , Anda tahu ini adalah set menguraikan, sehingga kemungkinan memukul salah satu pivot buruk hanya 2 - 2 α , dan 1 $n$$\alpha n$$(1-\alpha) n$$(1-\alpha) n$$\alpha > 1/2$$2 - 2\alpha$ .$1- 2 + 2\alpha=2\alpha - 1$