Teknik Desain · Pelajaran 4 dari 10
Divide and conquer
10 menit baca · BelajarCode
Divide and conquer terdiri dari tiga langkah:
- Divide: pecah masalah menjadi submasalah berukuran lebih kecil.
- Conquer: selesaikan setiap submasalah secara rekursif.
- Combine: gabungkan solusi submasalah menjadi solusi masalah awal.
Merge sort dan pencarian biner adalah contohnya. Berikut dua contoh lain.
Perpangkatan cepat
Menghitung aⁿ dengan perkalian berulang butuh n - 1 perkalian. Dengan divide and conquer: aⁿ = (a^(n/2))² jika n genap, dan a · a^(n-1) jika n ganjil.
1def pangkat(a, n, mod):2 if n == 0:3 return 14 if n % 2 == 0:5 setengah = pangkat(a, n // 2, mod)6 return setengah * setengah % mod7 return a * pangkat(a, n - 1, mod) % mod89print(pangkat(3, 13, 1000))10print(pangkat(2, 10**18, 1_000_000_007))11print(pow(2, 10**18, 1_000_000_007))323 719476260 719476260
Rekurensnya T(n) = T(n/2) + Θ(1), jadi Θ(log n). Pangkat 10¹⁸ cukup sekitar 60 langkah. pow bawaan Python memakai algoritma yang sama.
Jumlah subarray terbesar
Diberikan array bilangan (bisa negatif), cari jumlah terbesar dari subarray yang berurutan. Subarray terbaik bisa berada di separuh kiri, separuh kanan, atau melintasi tengah.
1def lintas_tengah(a, kiri, tengah, kanan):2 jumlah = 03 terbaik_kiri = float("-inf")4 for i in range(tengah, kiri - 1, -1):5 jumlah += a[i]6 terbaik_kiri = max(terbaik_kiri, jumlah)7 jumlah = 08 terbaik_kanan = float("-inf")9 for i in range(tengah + 1, kanan + 1):10 jumlah += a[i]11 terbaik_kanan = max(terbaik_kanan, jumlah)12 return terbaik_kiri + terbaik_kanan1314def subarray_terbesar(a, kiri, kanan):15 if kiri == kanan:16 return a[kiri]17 tengah = (kiri + kanan) // 218 return max(subarray_terbesar(a, kiri, tengah),19 subarray_terbesar(a, tengah + 1, kanan),20 lintas_tengah(a, kiri, tengah, kanan))2122data = [2, -4, 3, -1, 5, -9, 4, 2, -3]23print(subarray_terbesar(data, 0, len(data) - 1))7
Subarray terbaiknya [3, -1, 5] dengan jumlah 7. Rekurensnya T(n) = 2T(n/2) + Θ(n), jadi Θ(n log n). Masalah ini sebenarnya bisa diselesaikan dalam Θ(n) dengan dynamic programming (algoritma Kadane), dibahas di pelajaran dynamic programming.
Cek pemahaman
Kenapa perpangkatan cepat butuh Θ(log n) langkah?
Latihan
Menghitung inversi
Inversi adalah pasangan indeks i < j dengan a[i] > a[j]. Banyaknya inversi mengukur seberapa tidak urut sebuah array. Hitung inversi dalam Θ(n log n) dengan memodifikasi merge sort: saat elemen kanan diambil lebih dulu, semua elemen kiri yang tersisa membentuk inversi dengannya.
Pembahasan
1def urut_hitung(a):2 if len(a) <= 1:3 return a, 04 tengah = len(a) // 25 kiri, x = urut_hitung(a[:tengah])6 kanan, y = urut_hitung(a[tengah:])7 hasil, inversi = [], x + y8 i = j = 09 while i < len(kiri) and j < len(kanan):10 if kiri[i] <= kanan[j]:11 hasil.append(kiri[i])12 i += 113 else:14 hasil.append(kanan[j])15 inversi += len(kiri) - i16 j += 117 hasil += kiri[i:] + kanan[j:]18 return hasil, inversi1920print(urut_hitung([2, 4, 1, 3, 5])[1])21print(urut_hitung([5, 4, 3, 2, 1])[1])3 10
Pada [2, 4, 1, 3, 5], inversinya (2,1), (4,1), dan (4,3). Array terbalik berisi 5 elemen punya inversi maksimal 5 × 4 / 2 = 10.
Jalankan contoh kode di pelajaran ini tanpa instalasi lewat compiler Python online.