Berusaha memahami perbandingan 2N lnN untuk quicksort

Saya sedang melalui analisis quicksort dalam buku Algoritma Sedgewick. Dia menciptakan relasi pengulangan berikut untuk jumlah pembanding di quicksort sambil menyortir array N item yang berbeda.

Saya mengalami kesulitan memahami hal ini ... Saya tahu dibutuhkan 1 / N probabilitas untuk setiap elemen menjadi pivot dan bahwa jika k menjadi pivot, maka sub-array kiri akan memiliki elemen k-1 dan sub-kanan array akan memiliki elemen Nk.

1.Bagaimana biaya partisi menjadi N + 1? Apakah perlu N + 1 dibandingkan untuk melakukan partisi?

2.Sedgewick mengatakan, untuk setiap nilai k, jika Anda menjumlahkannya, probabilitas bahwa elemen partisi adalah k + biaya untuk dua sub-array Anda mendapatkan persamaan di atas.

• Adakah yang bisa menjelaskan hal ini sehingga mereka yang kurang pengetahuan matematika (saya) bisa mengerti?
• Secara khusus bagaimana Anda mendapatkan suku kedua dalam persamaan?
• Apa sebenarnya arti istilah itu?

Fungsi biaya Cuntuk quicksort terdiri dari dua bagian. Bagian pertama adalah biaya mempartisi array dalam dua 'bagian' (bagian tidak harus berukuran sama, maka kutip). Bagian kedua adalah biaya memilah kedua bagian.

1. The (N + 1)Istilah sebenarnya adalah sebuah istilah kental, dan berasal dari istilah

   (N - 1) + 2
   

   Ini adalah biaya partisi di quicksort: N-1bandingkan dengan nilai pivot, dan 2 perbandingan tambahan karena beberapa kondisi batas dalam partisi.

2. Bagian kedua dari persamaan terdiri dari biaya untuk menyortir dua 'bagian' di kedua sisi dari nilai pivot k.

   Setelah memilih nilai pivot, Anda dibiarkan dengan dua 'bagian' yang tidak disortir. Biaya penyortiran 'separuh' ini tergantung pada ukurannya dan paling mudah digambarkan sebagai aplikasi rekursif dari fungsi biaya C. Jika pivot adalah yang terkecil dari Nnilai - nilai, biaya untuk menyortir masing-masing dari dua 'bagian' masing C(0)- masing dan C(N-1)(biaya untuk menyortir array dengan 0 elemen dan biaya untuk menyortir satu dengan N-1elemen). Jika pivot adalah yang terkecil kelima, maka biaya untuk mengurutkan masing-masing dari dua 'bagian' adalah masing C(5)- masing dan C(N-6)(biaya untuk mengurutkan array dengan 5 elemen dan biaya untuk mengurutkan satu dengan N-6elemen). Dan juga untuk semua nilai pivot lainnya.

   Tetapi berapa biaya untuk mengurutkan kedua 'separuh' jika Anda tidak tahu nilai pivot? Ini dilakukan dengan mengambil biaya untuk setiap nilai pivot yang mungkin dan mengalikannya dengan kemungkinan bahwa nilai tertentu muncul.

   Karena setiap nilai pivot juga memiliki kemungkinan yang sama, peluang untuk memilih nilai pivot tertentu adalah 1/Njika Anda memiliki Nelemen. Untuk memahami ini, pikirkan tentang melempar dadu. Dengan dadu yang tepat, peluang bagi masing-masing pihak untuk menghadap ke atas adalah sama, sehingga peluang untuk melempar 1 adalah 1/6.

   Gabungan, ini memberikan istilah penjumlahan di mana, untuk setiap nilai yang mungkin k dari pivot, biaya ( C(k-1) + C(N-k)) dikalikan dengan kesempatan ( 1/N)

3. Derivasi lebih lanjut dari rumusan penjumlahan dalam pertanyaan ke 2N lnNdalam judul membutuhkan terlalu banyak matematika untuk dijelaskan di sini, tetapi didasarkan pada pemahaman bahwa biaya untuk menyortir berbagai Nelemen ( C(N)) dapat diekspresikan dalam hal menyortir suatu array N-1elemen ( C(N-1)) dan faktor yang berbanding lurus dengan N.

1. Tampaknya N +1 sebagai jumlah perbandingan untuk langkah partisi adalah kesalahan dalam buku ini. Anda perlu mencari tahu untuk masing-masing elemen N-1 non-pivot apakah lebih kecil atau lebih besar dari pivot, yang membutuhkan satu perbandingan; dengan demikian perbandingan N – 1 secara total, bukan N + 1. (Pertimbangkan kasus paling sederhana, N = 2, yaitu satu pivot dan satu elemen lainnya: Sama sekali tidak ada ruang untuk melakukan tiga perbandingan antara dua elemen.)

2. Pertimbangkan kasus di mana pivot yang dipilih kebetulan merupakan elemen terkecil (k = 1). Ini berarti bahwa array dibagi menjadi bagian kosong di sebelah kiri (tidak ada elemen yang kurang dari pivot) dan bagian di sebelah kanan yang berisi semua elemen kecuali untuk pivot (semua elemen lain lebih besar dari pivot ). Ini berarti bahwa sub-masalah yang Anda ingin selesaikan secara rekursi memiliki ukuran 0 dan N – 1 (k – 1 dan N – k), masing-masing, dan memerlukan perbandingan C (0) dan C (N – 1); dengan demikian, C (0) + C (N – 1) secara total.

   Jika pivot merupakan elemen terkecil kedua (k = 2), ukuran sub-masalah adalah 1 dan N – 2 (k – 1 dan N-k; satu elemen di sebelah kiri, karena itu adalah satu-satunya yang lebih kecil dari pivot). Dengan demikian, pemecahan sub-masalah ini secara rekursif membutuhkan perbandingan C (1) + C (N – 2). Dan seterusnya jika pivot adalah elemen terkecil ketiga, keempat, dll. Ini adalah ekspresi dalam pembilang.

   Karena pivot dipilih secara acak dari antara elemen N, setiap kasus (pivot terkecil, pivot terkecil kedua, dll.) Terjadi dengan probabilitas yang sama 1 / N. Dari situlah N dalam penyebut berasal.