Algoritma Divide and Conquer - Mengapa tidak membagi lebih dari dua bagian?

Dalam algoritma divide and conquer seperti quicksort dan mergesort, input biasanya (setidaknya dalam teks pengantar) dibagi menjadi dua , dan dua set data yang lebih kecil kemudian ditangani secara rekursif. Masuk akal bagi saya bahwa ini membuatnya lebih cepat untuk menyelesaikan masalah jika kedua belah pihak membutuhkan waktu kurang dari setengah pekerjaan berurusan dengan seluruh kumpulan data. Tetapi mengapa tidak membagi kumpulan data menjadi tiga bagian? Empat? n ?

Saya kira pekerjaan memecah data dalam banyak, banyak sub set membuatnya tidak layak, tetapi saya kurang intuisi untuk melihat bahwa seseorang harus berhenti di dua sub set.

Saya juga telah melihat banyak referensi untuk quicksort 3-arah. Kapan ini lebih cepat? Apa yang digunakan dalam praktik?

Masuk akal bagi saya bahwa ini membuatnya lebih cepat untuk menyelesaikan masalah jika kedua belah pihak membutuhkan waktu kurang dari setengah pekerjaan berurusan dengan seluruh kumpulan data.

Itu bukan inti dari algoritma divide-and-conquer. Biasanya intinya adalah bahwa algoritma tidak dapat "menangani seluruh set data" sama sekali. Alih-alih, itu dibagi menjadi beberapa bagian yang sepele untuk dipecahkan (seperti menyortir dua angka), kemudian dipecahkan secara sepele dan hasilnya digabungkan dengan cara yang menghasilkan solusi untuk set data lengkap.

Tetapi mengapa tidak membagi kumpulan data menjadi tiga bagian? Empat? n?

Terutama karena membaginya menjadi lebih dari dua bagian dan menggabungkan kembali lebih dari dua hasil menghasilkan implementasi yang lebih kompleks tetapi tidak mengubah karakteristik fundamental (Big O) dari algoritma - perbedaannya adalah faktor konstan, dan dapat mengakibatkan perlambatan jika pembagian dan rekombinasi lebih dari 2 himpunan bagian menciptakan overhead tambahan.

Misalnya, jika Anda melakukan semacam penggabungan 3 arah, maka pada fase rekombinasi Anda sekarang harus menemukan yang terbesar dari 3 elemen untuk setiap elemen, yang membutuhkan 2 perbandingan, bukan 1, sehingga Anda akan melakukan dua kali lebih banyak perbandingan secara keseluruhan . Sebagai gantinya, Anda mengurangi kedalaman rekursi dengan faktor ln (2) / ln (3) == 0,63, sehingga Anda memiliki swap lebih sedikit 37%, tetapi 2 * 0,63 == perbandingan 26% lebih banyak (dan akses memori). Apakah itu baik atau buruk tergantung pada mana yang lebih mahal di perangkat keras Anda.

Saya juga telah melihat banyak referensi untuk quicksort 3-arah. Kapan ini lebih cepat?

Rupanya varian dual pivot quicksort dapat dibuktikan membutuhkan jumlah perbandingan yang sama tetapi rata-rata 20% lebih sedikit swap, jadi ini merupakan keuntungan bersih.

Apa yang digunakan dalam praktik?

Dewasa ini hampir tidak ada orang yang memprogram algoritma sorting mereka sendiri lagi; mereka menggunakan satu yang disediakan oleh perpustakaan. Sebagai contoh, Java 7 API sebenarnya menggunakan quicksort dual-pivot.

Orang-orang yang benar-benar memprogram algoritma pengurutan mereka sendiri untuk beberapa alasan akan cenderung tetap berpegang pada varian 2-arah yang sederhana karena lebih sedikit potensi kesalahan mengalahkan kinerja 20% lebih baik sebagian besar waktu. Ingat: sejauh ini peningkatan kinerja yang paling penting adalah ketika kode beralih dari "tidak bekerja" menjadi "bekerja".

Berbicara asimtotik, tidak masalah. Misalnya, pencarian biner membuat  perbandingan log ₂ n, dan pencarian ternary membuat  perbandingan log ₃ n. Jika Anda mengetahui logaritma Anda, Anda tahu bahwa log _a  x = log _b  x / log _b  a, jadi pencarian biner hanya menghasilkan sekitar 1 / log ₃ 2 ≈ 1,5 kali lebih banyak perbandingan dari pencarian terner. Ini juga alasan mengapa tidak ada yang pernah menentukan basis logaritma dalam notasi Oh besar: Itu selalu merupakan faktor konstan jauh dari logaritma dalam basis yang diberikan, tidak peduli apa basis sebenarnya. Jadi memecah masalah menjadi lebih banyak himpunan bagian tidak meningkatkan kompleksitas waktu dan secara praktis tidak cukup untuk melebihi logika yang lebih kompleks. Faktanya, kompleksitas itu dapat memengaruhi kinerja praktis secara negatif, meningkatkan tekanan cache atau membuat optimisasi mikro menjadi lebih mudah.

Di sisi lain, beberapa struktur data tree-ish menggunakan faktor pencabangan tinggi (jauh lebih besar dari 3, sering 32 atau lebih), meskipun biasanya karena alasan lain. Ini meningkatkan pemanfaatan hirarki memori: struktur data yang disimpan dalam RAM membuat penggunaan cache lebih baik, struktur data yang disimpan dalam disk memerlukan lebih sedikit pembacaan HDD-> RAM.

Ada algoritma pencarian / sortir yang membagi bukan oleh dua, tetapi oleh N.

Contoh sederhana adalah pencarian dengan kode hash, yang membutuhkan O (1) waktu.

Jika fungsi hash adalah mempertahankan pesanan, itu dapat digunakan untuk membuat algoritma sortir O (N). (Anda dapat menganggap algoritme pengurutan apa pun sebagai hanya melakukan pencarian N di mana angka harus berada dalam hasil.)

Masalah mendasarnya adalah, ketika suatu program memeriksa beberapa data dan kemudian memasuki beberapa status berikut, berapa banyak status berikut ini di sana, dan seberapa dekat dengan persamaan probabilitas mereka?

Ketika komputer melakukan perbandingan dua angka, katakan, dan kemudian melompat atau tidak, jika kedua jalur sama-sama mungkin, penghitung program "tahu" satu bit informasi lagi di setiap jalur, jadi rata-rata komputer itu "mempelajari" satu angka. sedikit. Jika masalah mengharuskan bit M dipelajari, maka menggunakan keputusan biner itu tidak bisa mendapatkan jawaban dalam lebih sedikit dari keputusan M. Jadi, misalnya, mencari angka dalam tabel ukuran 1024 yang disortir tidak dapat dilakukan dalam lebih sedikit dari 10 keputusan biner, jika hanya karena lebih sedikit tidak akan memiliki hasil yang cukup, tetapi tentu saja dapat dilakukan dalam lebih dari itu.

Ketika komputer mengambil satu angka dan mengubahnya menjadi indeks menjadi sebuah array, ia "belajar" hingga mencatat basis 2 dari jumlah elemen dalam array, dan ia melakukannya dalam waktu yang konstan. Sebagai contoh, jika ada tabel lompatan 1024 entri, semua kemungkinan besar kurang lebih sama, maka melompat melalui tabel itu "belajar" 10 bit. Itulah trik mendasar di balik pengkodean hash. Contoh penyortiran ini adalah bagaimana Anda dapat mengurutkan setumpuk kartu. Memiliki 52 nampan, satu untuk setiap kartu. Masukkan setiap kartu ke dalam nampannya, lalu angkat semuanya. Tidak diperlukan pengelompokan ulang.

Karena ini adalah pertanyaan tentang perpecahan dan penaklukan umum, bukan hanya penyortiran, saya terkejut tidak ada yang mengemukakan Teorema Master

Singkatnya, waktu menjalankan algoritma divide and conquer ditentukan oleh dua kekuatan countervile: manfaat yang Anda dapatkan dari mengubah masalah yang lebih besar menjadi masalah kecil, dan harga yang Anda bayar karena harus menyelesaikan lebih banyak masalah. Bergantung pada detail algoritme, mungkin dapat atau tidak membayar untuk membagi masalah menjadi lebih dari dua bagian. Jika Anda membagi jumlah subproblem yang sama pada setiap langkah, dan Anda tahu kompleksitas waktu menggabungkan hasil pada setiap langkah, Teorema Master akan memberi tahu Anda kompleksitas waktu dari keseluruhan algoritma.

The Karatsuba algoritma untuk perkalian menggunakan membagi 3-way dan menaklukkan untuk mencapai waktu berjalan dari O (3 n ^ log_2 3) yang mengalahkan O (n ^ 2) untuk algoritma perkalian biasa (n adalah jumlah digit di angka).

Karena sifat binernya, sebuah komputer sangat efisien dalam membagi barang menjadi 2 dan tidak begitu banyak dalam 3. Anda mendapatkan pembagian dalam 3 dengan membagi 2 terlebih dahulu dan kemudian membagi salah satu bagian lagi menjadi 2. Jadi jika Anda perlu membagi dengan 2 untuk mendapatkan 3 divisi Anda, Anda mungkin juga membagi 2.