Memecahkan hubungan perulangan dengan dua panggilan rekursif

Saya sedang mempelajari runtime quicksort kasus terburuk dengan syarat bahwa ia tidak akan pernah melakukan partisi yang sangat tidak seimbang untuk berbagai definisi sangat .

Untuk melakukan ini, saya bertanya pada diri sendiri pertanyaan apa runtime $T(n, p)$ akan terjadi dalam kasus quicksort selalu terjadi pada partisi di sebagian kecil $0 < p \leq {1\over 2}$ sehingga$\lfloor{p(n-1)}\rfloor$berada di partisi kiri dan$\lceil(1 - p)(n - 1)\rceil$berada di partisi kanan (menyisakan$1$elemen, pivot, di tengah).

Seharusnya tidak sulit untuk melihat bahwa $T(n, p)$ memberikan batas atas untuk kasus terburuk di mana $p$ adalah partisi yang dibiarkan tidak seimbang secara maksimal, karena setiap partisi dengan fraksi $> p$ akan lebih seimbang dan memiliki runtime yang lebih kecil, dan fraksi apa pun $<p$ tidak diizinkan.

Sudah jelas bahwa $T(n, {1 \over 2})$adalah kasus terbaik dan$T(n, 0)$adalah kasus terburuk quicksort. Keduanya memiliki hubungan rekurensi yang mudah ditemukan dalam sumber daya pendidikan apa pun. Tapi saya tidak tahu bagaimana mempelajari$T(n, p)$secara umum. Hubungan yang jelas adalah:

Di sini saya macet. Saya sudah mencoba mencari di sekitar, tetapi semua literatur yang saya bisa mengerti tentang algoritma divide and conquer mengambil "divide" secara harfiah dan "menipu" analisis menggunakan fakta bahwa partisi selalu dalam ukuran yang sama, menggabungkan istilah menjadi satu kali konstan.

Saya tidak tahu bagaimana menangani dua panggilan rekursif, dan saya tidak tahu apakah aman untuk menghapus pembulatan. Apakah ini mungkin diselesaikan secara analitis, dan jika ya, bagaimana?

PS: Saya tidak tertarik pada asimptotik (yang mudah ditunjukkan untuk p konstan ). Saya tertarik pada seberapa cepat quicksort menjadi ketika p semakin kecil, misalnya saya tertarik pada rasio T ( n , 0,25 $\Theta(n \log n)$$p$$p$ .$T(n, 0.25) \over T(n, 0.5)$

PPS: Sebagai seorang mahasiswa sarjana, saya minta maaf jika saya telah membuat hal-hal yang nontrivialities terlalu panjang atau tidak jelas. Dan sementara saya tidak tahu apakah ini dipandang rendah seperti situs SE lainnya, saya akan perhatikan bahwa ini adalah kepentingan pribadi, bukan pekerjaan rumah.

Seperti yang Anda sebutkan, teorema Akra-Bazzi menunjukkan bahwa solusi untuk pengulangan $T(n,p)$ adalah untuk semua p ∈ ( 0 , 1 ) . Namun, ini tidak mengungkapkan sifat ketergantungan pada hal . Untuk menentukan yang terakhir, kita bisa menggunakan pendekatan pohon rekursi.$O(n\log n)$$p \in (0,1)$$p$

Pada akar pohon rekursi adalah interval . Dua anaknya adalah interval { 1 , ... , p n $\{1,\ldots n\}$$\{1,\ldots,pn\}$ dan , yang panjang totalnya lagi n . Masing-masing node memiliki dua anak (dengan asumsi n cukup besar), dan seterusnya. Untuk kesederhanaan kita mengabaikan kesalahan pembulatan, yaitu, kita menganggap bahwa p $\{pn+1,\ldots,n\}$$n$$n$$pn$adalah bilangan bulat; ini hanya masalah teknis, dan saya tidak akan mengkhawatirkannya. Kami menghentikan proses setiap kali satu simpul memiliki panjang paling banyak . Kompleksitas algoritma sebanding dengan total panjang interval di pohon. Ketika p ≠ 1 / 2 , yang daun (node di mana kita menghentikan proses) memiliki kedalaman yang berbeda, dan yang membuat lebih sulit untuk menentukan kompleksitas keseluruhan.$1$$p \neq 1/2$

Kita dapat memperoleh batas atas sederhana dengan mencatat bahwa pohon memiliki paling banyak tingkat : setiap node setidaknya merupakan faktor 1 - p lebih kecil dari induknya. Sama seperti dalam analisis untuk p = 1 / 2 , total panjang interval di tingkat manapun adalah paling n , dan kami memperoleh batas atas$\log_{1-p} (1/n)$$1-p$$p = 1/2$$n$ pada waktu berjalan. Sejak log 1 $O(n\log_{1-p} (1/n))$ danlog(1-p ) - 1 =-log(1-p)=p±O( p 2 )untukpkecil, kita dapat menulis ini sebagaiO(nlogn / p).$\log_{1-p} (1/n) = \log n/\log (1-p)^{-1}$$\log (1-p)^{-1} = -\log (1-p) = p \pm O(p^2)$$p$$O(n\log n/p)$

Berikut ini perhitungan yang lebih akurat. Pertimbangkan level . Misalkan kita tidak menghentikan proses setelah mencapai interval kecil. Kita dapat menghasilkan simpul acak dengan mengambil langkah t , di mana masing-masing kita ke kiri (katakanlah) dengan probabilitas p dan kanan (katakanlah) dengan probabilitas 1 - p . Setiap kali kita mengambil langkah ke kiri log dari panjang interval berkurang dengan - log p , dan setiap kali kita mengambil langkah yang tepat ia mengurangi by - log ( 1 - p ) . Sebuah vertex berada di pohon aktual dari log yang panjangnya berkurang paling banyak log $t$$t$$p$$1-p$$-\log p$$-\log (1-p)$$\log n$. Berat total interval pada level dari pohon adalah probabilitas tepat bahwa suatu simpul yang dihasilkan menurut proses ini sesuai dengan penurunan paling banyak log n . Yaitu, jika D adalah distribusi yang sama dengan - log p dengan probabilitas p dan to - log ( 1 - p ) dengan probabilitas 1 - p , dan X 1 , ... , X t ∼ D independen, maka total bobot dari level t adalah$t$$\log n$$D$$-\log p$$p$$-\log(1-p)$$1-p$$X_1,\ldots,X_t \sim D$$t$ . Untuk t super-konstan, variabel acak X 1 + ⋯ + X t kira-kira terdistribusi normal dengan rata-rata [ - p log p - ( 1 - p $\Pr[X_1+\cdots+X_t \leq \log n]$$t$$X_1+\cdots+X_t$ dan varians linier dalam t , jadi untuk tmemuaskan$[-p\log p-(1-p)\log(1-p)]t$$t$$t$ , katakanlah, probabilitas akan sangat dekat dengan 1 , sedangkan untuk t memuaskan [ - p log p - ( 1 - p ) log ( 1 - p ) ] t ≥ 2 log n , katakanlah, itu akan sangat mendekati nol. Mendefinisikan$[-p\log p-(1-p)\log(1-p)]t \leq (\log n)/2$$1$$t$$[-p\log p-(1-p)\log(1-p)]t \geq 2\log n$ (dikenal sebagai fungsi entropi biner), kami menyimpulkan bahwa waktu berjalan adalah Θ ( n log n / h ( p ) ) (seragam dalam p , seperti n → ∞ ). Sebagai p → 0 kita memiliki h ( p ) ≈ - p log $h(p) = -p\log p-(1-p)\log(1-p)$$\Theta(n\log n/h(p))$$p$$n\to\infty$$p\to 0$$h(p) \approx -p\log p$, dan perkiraan kami sebelumnya tidak ketat.

Cara lain untuk melihat pada analisis yang sama adalah dengan memiliki urutan yang tak terbatas dari variabel acak independen seperti sebelumnya, dan mendefinisikan menghentikan waktu T untuk menjadi pertama kalinya t sehingga X 1 + ⋯ + X t ≥ log n . Waktu berjalan kemudian sebanding dengan n E [ T ] . Teorema pembaruan dasar kemudian menyatakan bahwa lim n → ∞ E [ T ] $X_1,X_2,\ldots$$T$$t$$X_1 + \cdots + X_t \geq \log n$$n\mathbb{E}[T]$ , menyiratkan bahwa ukuran total interval sama dengan$\lim_{n\to\infty} \mathbb{E}[T]/\log n = 1/\mathbb{E}[D] = 1/h(p)$ . Lebih akurat, untuk setiap p konstan, ukuran total interval adalah ( 1 + α p ( n ) ) n log n / h ) , di mana$(1+o(1))n\log n/h(p)$$p$$(1+\alpha_p(n))n\log n/h(p)$ . Konvergensi dalam teorema pembaruan elementer adalah eksponensial dalam parameter waktu - log n dalam kasus kami - jadi harus polinomial dalam n , yaitu, α p ( n ) = O ( n - C p ) . Konvergensi juga mungkin seragam untuk p ∈ ( δ , 1 - δ ) untuk δ > 0 .$\alpha_p(n) = o(n)$$\log n$$n$$\alpha_p(n) = O(n^{-C_p})$$p \in (\delta,1-\delta)$$\delta > 0$

Ringkasnya, panjang total interval dalam pohon rekursi, yang sebanding dengan waktu berjalan, adalah dari bentuk berikut untuk setiap : T ( n , p ) = ( 1 + o ( 1 ) ) n log $p$manalogndanh(p)=-plogp-(1-p)log(1-p)dibawa ke basis yang sama, dano(1)adalah fungsi tergantung padapdan cenderung0dengann.

Selain itu, mungkin benar bahwa untuk dan p ∈ ( δ , 1 - δ ) memang benar bahwa total panjang interval adalah dalam bentuk T ( n , p ) = ( 1 + O ( n - C δ ) ) n log $\delta > 0$$p \in (\delta,1-\delta)$manaCδ>0dan konstanta O besar tersembunyi hanya bergantung padaδ. Secara khusus, harus demikian halnya untuk semua konstantap1,p2, limn→∞T(n,p1