Mengapa Quicksort Acak memiliki biaya runtime terburuk (O log n)

Penyortiran Cepat Acak adalah perpanjangan dari Penyortiran Cepat di mana elemen pivot dipilih secara acak. Apa yang bisa menjadi kompleksitas waktu terburuk dari algoritma ini. Menurut saya, itu harus , sebagai kasus terburuk terjadi ketika poros dipilih secara acak dipilih dalam diurutkan atau membalikkan diurutkan order. Tetapi dalam beberapa teks [1] [2] kompleksitas waktu terburuknya ditulis sebagai$O(n^2)$O ( n log n )$O(n\log{n})$

Apa yang benar

Kedua sumber Anda merujuk ke "waktu berjalan terburuk yang diharapkan" dariSaya menduga ini mengacu pada persyaratan waktu yang diharapkan, yang berbeda dari kasus terburuk absolut.$O(n \log n).$

Quicksort biasanya memiliki persyaratan mutlak waktu terburuk untuk . Kasus terburuk terjadi ketika, pada setiap langkah, prosedur partisi membagi array length menjadi array ukuran dan . Pemilihan elemen pivot "sial" ini membutuhkan panggilan rekursif, yang mengarah ke kasus terburuk .n 1 n - 1 O ( n ) O ( n 2$O(n^2)$$n$$1$$n-1$$O(n)$$O(n^2)$

Memilih pivot secara acak atau acak mengocok array sebelum penyortiran memiliki efek rendering kasus terburuk sangat tidak mungkin, terutama untuk array besar. Lihat Wikipedia untuk bukti bahwa persyaratan waktu yang diharapkan adalah . Menurut sumber lain , "probabilitas quicksort akan menggunakan jumlah kuadrat perbandingan ketika menyortir array besar di komputer Anda jauh lebih kecil daripada probabilitas bahwa komputer Anda akan terkena petir."$O(n\log n)$

Edit:

Per komentar Bangye, Anda dapat menghilangkan urutan pemilihan pivot kasus terburuk dengan selalu memilih elemen median sebagai pivot. Karena menemukan median membutuhkan waktu, ini memberikan kinerja kasus terburuk. Namun, karena quicksort acak sangat tidak mungkin untuk menemukan kasus terburuk, varian penentu median quicksort jarang digunakan.Θ ( n log n $O(n)$$\Theta(n \log n)$

Anda melewatkan teks-teks ini yang berbicara tentang " run time expected case terburuk ", bukan "runtime kasus terburuk".

Mereka sedang mendiskusikan implementasi Quicksort yang melibatkan elemen acak. Biasanya Anda memiliki algoritma deterministik, yaitu algoritma yang untuk input yang diberikan akan selalu menghasilkan langkah yang sama persis. Untuk menentukan "runtime kasus terburuk", Anda memeriksa semua input yang mungkin, dan memilih salah satu yang menghasilkan runtime terburuk.

Tetapi di sini kita memiliki faktor acak. Diberikan beberapa input, algoritma tidak akan selalu melakukan langkah yang sama karena beberapa keacakan terlibat. Alih-alih memiliki runtime untuk setiap input tetap, kami memiliki "runtime yang diharapkan" - kami memeriksa setiap nilai yang mungkin dari keputusan acak dan probabilitasnya, dan "runtime yang diharapkan" adalah rata-rata tertimbang dari runtime untuk setiap kombinasi keputusan acak , tetapi masih untuk input tetap.

Jadi kami menghitung "runtime yang diharapkan" untuk setiap input yang mungkin, dan untuk mendapatkan "runtime yang diharapkan terburuk", kami menemukan satu input yang mungkin di mana runtime yang diharapkan adalah yang terburuk. Dan ternyata mereka menunjukkan bahwa kasus terburuk untuk "runtime yang diharapkan" hanyalah O (n log n). Saya tidak akan terkejut jika hanya mengambil pivot pertama secara acak akan mengubah kasus terburuk yang diharapkan runtime menjadi o (n ^ 2) (sedikit o alih-alih Big O), karena hanya beberapa dari n pivot akan mengarah ke kasus terburuk tingkah laku.

Perhatikan bahwa ada dua hal yang perlu dilakukan ekspektasi / rata-rata: permutasi input dan pivot (satu per partisi).

$n$$\Theta(n \log n)$

$\Theta(n \log n)$

Intinya, periksa sumber Anda untuk implementasi yang mereka gunakan dan jumlah yang mereka anggap resp acak. diperbaiki dalam analisis mereka.

$O(n^2)$

Kasus terburuk untuk quicksort acak adalah elemen yang sama dengan input. Mis: 2,2,2,2,2,2

$T(n) = T(n-1) + n$$O(n^2)$