Dalam tutorial ini, Anda akan mempelajari cara kerja algoritma divide and conquer. Kami juga akan membandingkan pendekatan divide and conquer versus pendekatan lain untuk menyelesaikan masalah rekursif.
Sebuah membagi dan menaklukkan algoritma adalah strategi pemecahan masalah yang besar oleh
- memecah masalah menjadi sub-masalah yang lebih kecil
- memecahkan sub-masalah, dan
- menggabungkannya untuk mendapatkan hasil yang diinginkan.
Untuk menggunakan algoritma divide and conquer, digunakan rekursi . Pelajari tentang rekursi dalam berbagai bahasa pemrograman:
- Rekursi di Jawa
- Rekursi dengan Python
- Rekursi di C ++
Bagaimana Cara Kerja Bagi dan Taklukkan Algoritma?
Berikut langkah-langkahnya:
- Bagilah : Bagilah masalah yang diberikan menjadi sub-masalah menggunakan rekursi.
- Taklukkan : Selesaikan sub-masalah kecil secara rekursif. Jika submasalah cukup kecil, maka selesaikan secara langsung.
- Gabungkan: Gabungkan solusi dari sub-masalah yang merupakan bagian dari proses rekursif untuk menyelesaikan masalah yang sebenarnya.
Mari kita pahami konsep ini dengan bantuan sebuah contoh.
Di sini, kita akan mengurutkan sebuah array menggunakan pendekatan divide and conquer (mis. Merge sort).
- Biarkan array yang diberikan menjadi:
Array for merge sort - Bagilah larik menjadi dua bagian.
Bagilah array menjadi dua subbagian
Sekali lagi, bagi setiap sub bagian secara rekursif menjadi dua bagian sampai Anda mendapatkan elemen individual.
Bagilah larik menjadi beberapa subbagian yang lebih kecil - Sekarang, gabungkan elemen individu dengan cara yang diurutkan. Di sini, taklukkan dan gabungkan langkah-langkah berdampingan.
Gabungkan subbagian
Kompleksitas Waktu
Kompleksitas algoritma divide and conquer dihitung menggunakan teorema master.
T (n) = aT (n / b) + f (n), di mana, n = ukuran input a = jumlah submasalah dalam rekursi n / b = ukuran setiap subproblem. Semua subproblem diasumsikan memiliki ukuran yang sama. f (n) = biaya pekerjaan yang dilakukan di luar panggilan rekursif, yang meliputi biaya membagi masalah dan biaya penggabungan solusi
Mari kita ambil contoh untuk menemukan kompleksitas waktu dari masalah rekursif.
Untuk jenis gabungan, persamaan dapat ditulis sebagai:
T (n) = aT (n / b) + f (n) = 2T (n / 2) + O (n) Di mana, a = 2 (setiap kali, suatu masalah dibagi menjadi 2 subproblem) n / b = n / 2 (ukuran setiap sub masalah adalah setengah dari masukan) f (n) = waktu yang dibutuhkan untuk membagi masalah dan menggabungkan subproblem T (n / 2) = O (n log n) (Untuk memahami ini, silakan merujuk ke teorema master.) Sekarang, T (n) = 2T (n log n) + O (n) ≈ O (n log n)
Bagi dan Taklukkan Vs Pendekatan Dinamis
Pendekatan divide and conquer membagi masalah menjadi subproblem yang lebih kecil; sub-masalah ini diselesaikan lebih lanjut secara rekursif. Hasil dari setiap subproblem tidak disimpan untuk referensi di masa mendatang, sedangkan dalam pendekatan dinamis, hasil dari setiap subproblem disimpan untuk referensi di masa mendatang.
Gunakan pendekatan divide and conquer ketika masalah yang sama tidak diselesaikan berkali-kali. Gunakan pendekatan dinamis jika hasil subproblem akan digunakan beberapa kali di masa mendatang.
Mari kita pahami ini dengan sebuah contoh. Misalkan kita mencoba mencari deret Fibonacci. Kemudian,
Pendekatan Divide and Conquer:
fib (n) Jika n <2, return 1 Else, return f (n - 1) + f (n -2)
Pendekatan dinamis:
mem = () fib (n) If n in mem: return mem (n) else, If n <2, f = 1 else, f = f (n - 1) + f (n -2) mem (n) = f kembali f
Dalam pendekatan dinamis, mem menyimpan hasil dari setiap subproblem.
Keuntungan Algoritma Divide and Conquer
- Kompleksitas perkalian dua matriks dengan metode naif adalah O (n 3 ), sedangkan menggunakan pendekatan divide and conquer (yaitu perkalian matriks Strassen) adalah O (n 2,8074 ). Pendekatan ini juga menyederhanakan masalah lain, seperti Menara Hanoi.
- Pendekatan ini cocok untuk sistem multiprosesing.
- Itu membuat penggunaan cache memori secara efisien.
Bagi dan Taklukkan Aplikasi
- Pencarian Biner
- Gabungkan Sortir
- Sortir Cepat
- Perkalian Matriks Strassen
- Algoritma Karatsuba
