Dalam tutorial ini, anda akan belajar bagaimana algoritma membahagi dan menakluk berfungsi. Kami juga akan membandingkan pendekatan membahagi dan menakluk berbanding pendekatan lain untuk menyelesaikan masalah berulang.
A algoritma pecah dan perintah merupakan strategi penyelesaian masalah yang besar oleh
- memecahkan masalah menjadi sub-masalah yang lebih kecil
- menyelesaikan sub-masalah, dan
- menggabungkan mereka untuk mendapatkan output yang diinginkan.
Untuk menggunakan algoritma divide and winer, rekursi digunakan. Ketahui mengenai rekursi dalam bahasa pengaturcaraan yang berbeza:
- Pengulangan di Jawa
- Kembara di Python
- Pengulangan dalam C ++
Bagaimana Membahagi dan Menaklukan Algoritma?
Berikut adalah langkah-langkah yang terlibat:
- Bagilah : Bahagikan masalah yang diberikan kepada sub-masalah menggunakan pengulangan.
- Conquer : Selesaikan sub-masalah yang lebih kecil secara berulang. Sekiranya masalah kecil cukup kecil, maka selesaikan secara langsung.
- Gabungkan: Gabungkan penyelesaian sub-masalah yang merupakan sebahagian daripada proses rekursif untuk menyelesaikan masalah yang sebenarnya.
Mari kita fahami konsep ini dengan bantuan contoh.
Di sini, kita akan menyusun susunan menggunakan pendekatan membahagi dan menakluk (iaitu menyatukan gabungan).
- Biarkan susunan yang diberikan:
Array untuk penggabungan - Bahagikan susunan menjadi dua bahagian.
Bahagikan susunan menjadi dua bahagian
Sekali lagi, bahagikan setiap bahagian secara berulang ke dalam dua bahagian sehingga anda mendapat unsur-unsur individu.
Bahagikan susunan menjadi bahagian yang lebih kecil - Sekarang, gabungkan unsur-unsur individu secara tersusun. Di sini, menakluk dan menggabungkan langkah-langkah berdampingan.
Gabungkan bahagian-bahagiannya
Kerumitan Masa
Kerumitan algoritma pembahagi dan penaklukan dikira menggunakan teorema induk.
T (n) = aT (n / b) + f (n), di mana, n = ukuran input a = bilangan sub-masalah dalam pengulangan n / b = ukuran setiap sub-masalah. Semua masalah diandaikan mempunyai ukuran yang sama. f (n) = kos kerja yang dilakukan di luar panggilan rekursif, yang merangkumi kos membahagi masalah dan kos penggabungan penyelesaian
Mari kita ambil contoh untuk mencari kerumitan masa dari masalah berulang.
Untuk penggabungan, persamaan boleh ditulis sebagai:
T (n) = aT (n / b) + f (n) = 2T (n / 2) + O (n) Di mana, a = 2 (setiap kali, masalah dibahagikan kepada 2 subproblem) n / b = n / 2 (ukuran setiap sub masalah adalah separuh daripada input) f (n) = masa yang diambil untuk membahagikan masalah dan penggabungan sub-masalah T (n / 2) = O (n log n) (Untuk memahami ini, sila rujuk theorem induk.) Sekarang, T (n) = 2T (n log n) + O (n) ≈ O (n log n)
Divide and Conquer Vs pendekatan dinamik
Pendekatan pembahagi dan penaklukan membahagikan masalah kepada sub-masalah yang lebih kecil; sub-masalah ini diselesaikan secara berulang secara berulang. Hasil dari setiap sub masalah tidak disimpan untuk rujukan di masa depan, sedangkan, dalam pendekatan dinamis, hasil dari setiap sub masalah disimpan untuk rujukan di masa depan.
Gunakan pendekatan membahagi dan menakluk apabila masalah yang sama tidak diselesaikan berkali-kali. Gunakan pendekatan dinamik apabila hasil dari subproblem akan digunakan berkali-kali di masa depan.
Mari kita fahami ini dengan contoh. Andaikan kita berusaha mencari siri Fibonacci. Kemudian,
Bahagikan dan Menakluk pendekatan:
fib (n) Jika n <2, pulangkan 1 Lain, pulangkan f (n - 1) + f (n -2)
Pendekatan dinamik:
mem = () fib (n) Jika n dalam mem: kembali mem (n) lain, Jika n <2, f = 1 yang lain, f = f (n - 1) + f (n -2) mem (n) = f kembali f
Dalam pendekatan yang dinamik, mem menyimpan hasil setiap sub masalah.
Kelebihan Membahagi dan Menaklukkan Algoritma
- Kerumitan untuk pendaraban dua matriks menggunakan kaedah naif adalah O (n 3 ), sedangkan menggunakan pendekatan divide and winer (iaitu pendaraban matriks Strassen) adalah O (n 2.8074 ). Pendekatan ini juga memudahkan masalah lain, seperti Menara Hanoi.
- Pendekatan ini sesuai untuk sistem multiprosesan.
- Ia menggunakan cache memori dengan cekap.
Membahagi dan Menakluk Aplikasi
- Pencarian Perduaan
- Gabungkan Susun
- Susun Pantas
- Pendaraban Matriks Strassen
- Algoritma Karatsuba
