Recursive Searching and Sorting
Diperkenalkan| English | Makna |
|---|---|
| divide-and-conquer/dɪˈvaɪd ænd ˈkɒŋkə/ | bagi dan taklukkan |
| merge sort/mɜːdʒ sɔːt/ | pengurutan penggabungan |
| merge/mɜːdʒ/ | penggabungan |
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 splits into halves, then merges up
Single elements are sorted (base case); merges combine them upward.
Recursive binary search recurses on...
Kesulitan 1/5 · 100 koin + bonus kecil pada penyelesaian pertama hari ini
The target is only on one side of the middle.
Merge sort recurses on...
Kesulitan 1/5 · 100 koin + bonus kecil pada penyelesaian pertama hari ini
Sort each half, then merge the two sorted halves.
The base case for merge sort is an array of...
Kesulitan 1/5 · 100 koin + bonus kecil pada penyelesaian pertama hari ini
One (or zero) element needs no sorting.
Merge sort's running time is about...
Kesulitan 1/5 · 100 koin + bonus kecil pada penyelesaian pertama hari ini
log n levels of splitting, n work per level.
Both recursive binary search and merge sort are divide-and-conquer algorithms.
Kesulitan 1/5 · 100 koin + bonus kecil pada penyelesaian pertama hari ini
Both split the problem in half and recurse.
Order the merge step for halves [1,3] and [2,4].
Kesulitan 3/5 · 200 koin + bonus kecil pada penyelesaian pertama hari ini
Always take the smaller front element: 1, 2, 3, 4.