Pencarian dan Pengurutan Rekursif
| English | Bahasa Indonesia |
|---|---|
| divide-and-conquer/dɪˈvaɪd ænd ˈkɒŋkə/ | bagi dan taklukkan |
| merge sort/mɜːdʒ sɔːt/ | pengurutan gabung |
| merge/mɜːdʒ/ | bergabung |
Resursi bertemu pencarian dan urutan
- Ide bagi-dan-kuasai yang sama menggerakkan pencarian biner rekursif dan urutan gabung.
- Belah masalah menjadi dua, selesaikan bagian-bagiannya, gabungkan.
- Pencarian biner rekursif mencari salah satu bagian dengan memanggil dirinya sendiri padanya.
- Urutan gabung mengurutkan masing-masing bagian, lalu menggabungkan bagian-bagian terurut bersama.
Pencarian biner rekursif
- Kasus dasar: rentang kosong berarti target tidak ditemukan.
- Lihat tengah. Jika itu target, kembalikan indeksnya.
- Jika target lebih kecil, berresursi pada bagian kiri; jika lebih besar, bagian kanan.
- Setiap panggilan membelah dua rentang —
O(log n)yang sama, ditulis secara rekursif.
Urutan gabung
- Belah array menjadi dua bagian; urutkan masing-masing bagian secara rekursif.
- Kasus dasar: array dengan 0 atau 1 elemen sudah terurut.
- Menggabungkan: berjalan di kedua bagian terurut, selalu mengambil elemen depan yang lebih kecil.
- Jauh lebih cepat daripada urutan
n²— sekitarn log nbeban kerja.
Mengapa bagi-dan-kuasai menang
- Membelah dua masalah setiap langkah memberikan faktor
log n. n log nurutan gabung mengalahkan urutan seleksi/sisipann²pada array besar.- Kasus dasar (kosong atau satu elemen) menghentikan setiap cabang.
- Bentuk yang sama dengan semua resursi: belah turun, gabung naik kembali.
Pencarian biner rekursif berresursi pada SATU bagian (target hanya ada di satu sisi); urutan gabung berresursi pada KEDUA bagian dan kemudian menggabungkannya. Keduanya memerlukan kasus dasar — rentang kosong berarti "tidak ditemukan" untuk pencarian; array 0 atau 1 elemen sudah terurut untuk urutan gabung. Bagi-dan-kuasai inilah yang membuat mereka cepat (O(log n) dan O(n log n)).
Mengurutkan-gabung [3, 1, 2, 4]:
- Belah menjadi
[3, 1]dan[2, 4]; urangkan masing-masing →[1, 3]dan[2, 4]. - Gabung: ambil 1, lalu 2, lalu 3, lalu 4 →
[1, 2, 3, 4]. - Setiap penggabungan memilih elemen terdepan yang lebih kecil secara bergantian.
Pencarian biner rekursif melakukan rekursi pada satu separuh (kasus dasar: rentang kosong = tidak ditemukan) untuk O(log n) pencarian. Sortir gabungan melakukan rekursi pada kedua separuh dan menggabungkan mereka (kasus dasar: 0 atau 1 elemen) untuk O(n log n) penyortiran. Keduanya adalah bagi-dan-menaklukkan: pecah ke bawah, gabungkan kembali ke atas — jauh lebih cepat dari n².
Merge sort memecah menjadi dua bagian, lalu menggabungkan naik
Elemen tunggal sudah terurut (kasus dasar); penggabungan menggabungkannya naik.
Pencarian biner rekursif recurses pada...
Target hanya berada di satu sisi dari nilai tengah.
Merge sort recurses pada...
Urutkan setiap bagian, lalu gabungkan dua bagian yang sudah terurut.
Kasus dasar untuk merge sort adalah array yang...
Satu (atau nol) elemen tidak perlu diurutkan.
Waktu eksekusi merge sort adalah sekitar...
log n tingkat pemecahan, n pekerjaan per tingkat.
Kedua pencarian biner rekursif dan merge sort adalah algoritma bagi-dan-menaklukkan.
Keduanya memecah masalah menjadi dua dan melakukan rekursi.
Urutkan langkah penggabungan untuk bagian [1,3] dan [2,4].
Selalu ambil elemen depan yang lebih kecil: 1, 2, 3, 4.