Belajar Algoritm - Divide & Conquer Lanjut

#Pendahuluan

Setelah di episode 8 kita menguasai Binary Search dan varian-varian divide & conquer untuk searching, pada episode ini kita melihat aplikasi divide & conquer yang lebih kompleks — algoritma yang menyelesaikan masalah dengan sub-masalah yang lebih rumit daripada sekadar membagi array dua.

Mengapa divide & conquer lanjut penting? Karena banyak masalah fundamental — closest pair, perkalian matrix, dan FFT — memiliki solusi divide & conquer yang jauh lebih cepat dari brute force. Memahami bagaimana mereka bekerja akan memperkaya pola pikir kalian dalam merancang algoritma.

#Closest Pair of Points (O(n log n))

Closest pair mencari pasang titik dengan jarak Euclidean terkecil di 2D. Brute force: O(n²) — cek semua pasang. Divide & conquer: O(n log n).

#Strategi

Bagi: Sort titik berdasarkan koordinat x. Garis vertikal membagi menjadi dua setengah.
Konquer: Rekursif cari closest pair di masing-masing setengah (δ₁ dan δ₂). Ambil δ = min(δ₁, δ₂).
Gabung: Periksa strip — titik-titik yang jarak horizontalnya kurang dari δ dari garis pembagi. Di strip, cukup periksa maksimal 7 titik berikutnya per titik (bukan semua pasang).

python

import math
 
def closest_pair(points):
    points = sorted(points, key=lambda p: p[0])
    return _closest_rec(points)
 
def _closest_rec(pts):
    if len(pts) <= 3:
        return min(dist(pts[i], pts[j]) 
                   for i in range(len(pts)) 
                   for j in range(i + 1, len(pts)))
    
    mid = len(pts) // 2
    mid_x = pts[mid][0]
    
    dl = _closest_rec(pts[:mid])
    dr = _closest_rec(pts[mid:])
    d = min(dl, dr)
    
    # Strip: titik dengan |x - mid_x| < d
    strip = [p for p in pts if abs(p[0] - mid_x) < d]
    strip.sort(key=lambda p: p[1])  # sort by y
    
    # Periksa maksimal 7 titik berikutnya per titik
    for i in range(len(strip)):
        for j in range(i + 1, min(i + 8, len(strip))):
            d = min(d, dist(strip[i], strip[j]))
    return d
 
def dist(p1, p2):
    return math.sqrt((p1[0] - p2[0]) ** 2 + (p1[1] - p2[1]) ** 2)

Kunci optimasi: di strip, titik diurutkan berdasarkan y, dan hanya perlu memeriksa maksimal 7 titik berikutnya per titik — karena dalam kotak δ × 2δ, maksimal 8 titik bisa muat tanpa ada dua yang jaraknya kurang dari δ.

Note

Closest pair divide & conquer adalah contoh di mana gabungan (strip check) memerlukan informasi dari kedua sub-masalah. Tidak seperti merge sort yang gabungannya independent, di sini kita perlu "menyilang" informasi kiri-kanan — tetapi dengan batasan yang menjaga kompleksitas tetap O(n).

#Strassen Matrix Multiplication

Perkalian matrix konvensional: O(n³). Strassen (1969) mengurangi eksponen dari 3 menjadi log₂(7) ≈ 2.807.

#Ide Inti

Untuk mengalikan dua matrix 2×2:

plaintext

[a b]   [e f]   [ae+bg  af+bh]
[c d] × [g h] = [ce+dg  cf+dh]

Konvensional: 8 perkalian, 4 penjumlahan. Strassen menggunakan 7 perkalian dan lebih banyak penjumlahan/subtraksi — tetapi 7 < 8, dan rekursi T(n) = 7T(n/2) + Θ(n²) menghasilkan Θ(n^2.807) menurut Master Theorem.

Strassen bekerja dengan mendefinisikan 7 matrix intermediate M1-M7 yang cerdik, lalu menggabungkannya untuk menghasilkan hasil perkalian.

Warning

Meskipun Strassen secara teoritis lebih cepat, implementasi praktisnya sering kalah dari O(n³) konvensional untuk matrix kecil (< 256×256) karena overhead konstanta dan cache performance. Strassen menjadi unggul untuk matrix sangat besar — dan di sinilah library seperti BLAS/LAPACK mengoptimasi campuran keduanya.

#Cooley-Tukey FFT (Overview)

Fast Fourier Transform mengubah polynomial dari representasi koefisien ke representasi nilai (atau sebaliknya) dalam O(n log n) — bukan O(n²) secara konvensional.

#Mengapa FFT Penting

FFT adalah salah satu algoritma paling berdampak dalam sejarah komputer:

Multiplication polynomial: O(n log n) menggunakan FFT, bukan O(n²).
Signal processing: konversi time-domain ↔ frequency-domain.
Convolution: operasi fundamental di image processing dan deep learning.
Number-theoretic transform: dasar perkalian integer besar.

Strateginya: gunakan akar-akar n-th dari satu sebagai titik evaluasi, bagi polynomial menjadi bagian genap dan ganjil, lalu rekursif. T(n) = 2T(n/2) + Θ(n) → O(n log n).

#Perbandingan Divide & Conquer

Masalah	Brute Force	Divide & Conquer
Closest pair	O(n²)	O(n log n)
Matrix multiplication	O(n³)	O(n^2.807) — Strassen
Polynomial multiplication	O(n²)	O(n log n) — FFT

Di ketiga kasus, divide & conquer memberikan penghematan signifikan — dari eksponen yang lebih rendah hingga menambahkan faktor log n.

#Penutup

Pada episode 9 ini, kalian telah memahami:

Closest pair: O(n log n) dengan strip optimization — maksimal 7 titik per titik.
Strassen: O(n^2.807) — 7 perkalian vs 8 konvensional, rekursi mengurangi eksponen.
FFT: O(n log n) — fundamental untuk polynomial multiplication dan signal processing.
Divide & conquer lanjut menunjukkan power paradigma ini melampaui sorting dan searching.

Di episode 10 selanjutnya kita akan membahas Sliding Window & Two Pointer — dua teknik efisien untuk array/string yang menghindari brute force O(n²) dengan memanfaatkan struktur data linear. Sampai jumpa di episode 10!