Analisis · Pelajaran 3 dari 10
Rekurens dan teorema master
11 menit baca · BelajarCode
Waktu jalan algoritma rekursif dinyatakan dengan relasi rekurens. Merge sort, misalnya, membagi masalah berukuran n menjadi dua submasalah berukuran n/2, lalu menggabungkan dalam waktu Θ(n):
T(n) = 2T(n/2) + Θ(n), dengan T(1) = Θ(1).
Metode pohon rekursi
Gambarkan pekerjaan di setiap tingkat rekursi:
| Tingkat | Banyak submasalah | Ukuran tiap submasalah | Pekerjaan per tingkat |
|---|---|---|---|
| 0 | 1 | n | n |
| 1 | 2 | n/2 | n |
| 2 | 4 | n/4 | n |
| k | 2ᵏ | n/2ᵏ | n |
| log₂ n | n | 1 | n |
Ada sekitar log₂ n + 1 tingkat, masing-masing mengerjakan n. Totalnya Θ(n log n).
Teorema master
Untuk rekurens berbentuk T(n) = a·T(n/b) + f(n) dengan a ≥ 1 dan b > 1, bandingkan f(n) dengan n^(log_b a):
| Kasus | Syarat | Hasil |
|---|---|---|
| 1 | f(n) = O(n^(log_b a - ε)) untuk suatu ε > 0 | T(n) = Θ(n^(log_b a)) |
| 2 | f(n) = Θ(n^(log_b a)) | T(n) = Θ(n^(log_b a) · log n) |
| 3 | f(n) = Ω(n^(log_b a + ε)) dan a·f(n/b) ≤ c·f(n) untuk suatu c < 1 | T(n) = Θ(f(n)) |
| Algoritma | Rekurens | n^(log_b a) | Kasus | Hasil |
|---|---|---|---|---|
| Pencarian biner | T(n) = T(n/2) + Θ(1) | n⁰ = 1 | 2 | Θ(log n) |
| Merge sort | T(n) = 2T(n/2) + Θ(n) | n | 2 | Θ(n log n) |
| Perkalian Karatsuba | T(n) = 3T(n/2) + Θ(n) | n^1,585 | 1 | Θ(n^1,585) |
| Contoh kasus 3 | T(n) = 2T(n/2) + Θ(n²) | n | 3 | Θ(n²) |
Memeriksa secara numerik
1import math2from functools import lru_cache34@lru_cache(maxsize=None)5def T(n):6 if n <= 1:7 return 18 return 2 * T(n // 2) + n910for k in [10, 15, 20]:11 n = 2 ** k12 print(f"n=2^{k}: T(n)={T(n)}, T(n)/(n log n)={T(n) / (n * math.log2(n)):.3f}")n=2^10: T(n)=11264, T(n)/(n log n)=1.100 n=2^15: T(n)=524288, T(n)/(n log n)=1.067 n=2^20: T(n)=22020096, T(n)/(n log n)=1.050
Rasionya mendekati konstanta 1, menguatkan bahwa T(n) = Θ(n log n).
Tidak semua rekurens bisa diselesaikan teorema master
Teorema master hanya berlaku untuk bentuk aT(n/b) + f(n). Rekurens seperti T(n) = T(n - 1) + n (misalnya quick sort pada kasus terburuk) diselesaikan dengan menjumlahkan langsung: n + (n - 1) + ... + 1 = Θ(n²).
Cek pemahaman
Berapa solusi T(n) = 4T(n/2) + n menurut teorema master?
Latihan
Tiga rekurens
Selesaikan rekurens berikut dengan teorema master: (a) T(n) = 8T(n/2) + n², (b) T(n) = T(n/2) + n, (c) T(n) = 2T(n/4) + √n.
Pembahasan
- (a) a = 8, b = 2, n^(log₂ 8) = n³. f(n) = n² lebih kecil secara polinomial, kasus 1: Θ(n³).
- (b) a = 1, b = 2, n^(log₂ 1) = n⁰ = 1. f(n) = n lebih besar secara polinomial, dan syarat keteraturan terpenuhi karena f(n/2) = n/2 ≤ (1/2)·n. Kasus 3: Θ(n).
- (c) a = 2, b = 4, n^(log₄ 2) = n^(1/2) = √n. f(n) = √n setara, kasus 2: Θ(√n log n).
Jalankan contoh kode di pelajaran ini tanpa instalasi lewat compiler Python online.