🚀

Desain dan Analisis Algoritma

Algoritma Divide and Conquer
Lanjutan

Closest Pair · Karatsuba · BFPRT · FFT · Analisis Lanjut

O(n)

BFPRT

O(n log n)

Closest Pair

O(n^1.585)

Karatsuba

FFT

Konvolusi Cepat

Agenda Lanjutan

Fokus Materi

1. Mengapa materi lanjutan penting?

Saat Master Theorem tidak cukup dan masalah makin kompleks

2. Closest Pair of Points

Contoh geometri komputasi O(n log n)

3. Karatsuba Multiplication

3 perkalian menggantikan 4 perkalian

4. BFPRT / Median of Medians

Seleksi median worst-case linear

5. FFT

Perkalian polinomial dan konvolusi cepat

6. Analisis rekurens lanjutan

Saat Master Theorem tidak langsung berlaku

Motivasi

Mengapa Perlu Materi Lanjutan?

🧠

Masalah lebih kaya

D&C tidak hanya sorting dan searching; ia dipakai pada geometri, aljabar, sinyal, dan seleksi statistik.

📉

Kompleksitas lebih tajam

Beberapa algoritma lanjutan memecahkan batas naive, misalnya Karatsuba dari O(n²) ke O(n^1.585).

📐

Analisis lebih sulit

Tidak semua rekurens cocok langsung dengan Master Theorem; perlu pohon rekursi atau pembuktian induksi.

Materi lanjutan biasanya muncul setelah mahasiswa memahami Merge Sort, Quick Sort, dan Binary Search, lalu naik ke contoh yang menggabungkan ide pembagian cerdas, batas geometri, dan pemilihan pivot deterministik.

Closest Pair

Closest Pair of Points

Masalah: diberikan n titik pada bidang 2D, cari dua titik dengan jarak Euclidean minimum. Pendekatan brute force memeriksa semua pasangan dan butuh O(n²).

Ide Divide and Conquer

• Urutkan titik berdasarkan koordinat x.
• Bagi menjadi dua bagian di median x.
• Hitung jarak minimum kiri = d1, kanan = d2.
• Ambil d = min(d1, d2), lalu cek strip selebar d di sekitar garis pembagi.
• Berkat packing lemma, tiap titik hanya dibandingkan dengan paling banyak sekitar 6 titik berikutnya pada urutan y.

// Rekurens Closest Pair T(n) = 2T(n/2) + O(n) // Karena: // - dua submasalah ukuran n/2 // - merge step linear setelah preprocessing => T(n) = O(n log n) Aplikasi: - GIS / pemetaan - robotika - collision detection - clustering spasial

Karatsuba

Karatsuba Multiplication

Jika x dan y adalah bilangan n-digit, perkalian biasa memerlukan 4 perkalian submasalah ketika dipecah menjadi dua bagian: x = x1·2^(n/2) + x0 dan y = y1·2^(n/2) + y0.

Trik Karatsuba

• a = x1y1
• b = x0y0
• p = (x1 + x0)(y1 + y0)
• Bagian tengah = p - a - b

Hanya butuh 3 perkalian rekursif, bukan 4.

x = x1·2^(n/2) + x0 y = y1·2^(n/2) + y0 xy = a·2^n + (p-a-b)·2^(n/2) + b a = x1y1 b = x0y0 p = (x1+x0)(y1+y0) Rekurens: T(n) = 3T(n/2) + cn Dengan Master Theorem: T(n) = O(n^(log2 3)) ≈ O(n^1.585)

Seleksi Deterministik

BFPRT / Median of Medians

1️⃣

Kelompok 5

Bagi data menjadi grup berukuran 5, urutkan tiap grup, ambil median tiap grup.

2️⃣

Median dari median

Cari median dari daftar median sebagai pivot deterministik yang dijamin “cukup baik”.

3️⃣

Partisi & rekursi

Buang bagian besar input; paling buruk ukuran sisa hanya sekitar 7n/10 + 6.

Rekurens BFPRT: T(n) ≤ T(n/5) + T(7n/10 + 6) + cn Master Theorem tidak langsung berlaku. Namun bisa dibuktikan: T(n) = O(n)

Keunggulan utama BFPRT adalah memberikan worst-case linear time untuk masalah seleksi (misalnya mencari median atau elemen ke-k). Ini penting ketika Quickselect bisa jatuh ke kasus buruk.

Inti ide: pilih pivot yang dijamin tidak terlalu ekstrem.

FFT

Fast Fourier Transform

FFT adalah teknik Divide and Conquer untuk mengevaluasi polinomial secara cepat pada akar-akar kesatuan. Ide utamanya: pisahkan koefisien indeks genap dan ganjil.

Pemisahan

P(x) = P_even(x²) + x·P_odd(x²)

• Bagi polinomial ukuran n menjadi dua polinomial ukuran n/2.
• Evaluasi rekursif pada titik yang sesuai.
• Gabungkan dalam waktu linear.

Kompleksitas

T(n) = 2T(n/2) + O(n) => T(n) = O(n log n)

Aplikasi FFT:

• Perkalian polinomial cepat
• Konvolusi pada audio dan citra
• Kompresi dan pemrosesan sinyal
• Komunikasi digital dan analisis frekuensi

Analisis Lanjut

Saat Master Theorem Tidak Cukup

Kasus yang mudah

• Merge Sort: T(n)=2T(n/2)+n
• Karatsuba: T(n)=3T(n/2)+n
• FFT: T(n)=2T(n/2)+n

Semua cocok dengan bentuk aT(n/b)+f(n).

Kasus yang lebih sulit

• BFPRT: T(n/5) + T(7n/10+6) + cn
• Ukuran submasalah tidak simetris
• Ada konstanta tambahan +6
• Tidak langsung masuk 3 kasus Master Theorem standar

Solusi: pohon rekurensi, substitusi, atau pembuktian induksi.

Pelajaran penting: dalam materi lanjutan, mahasiswa bukan hanya menghafal rumus, tetapi belajar memahami struktur pembagian masalah dan memilih teknik analisis yang sesuai.

Ringkasan Kompleksitas

Peta Algoritma Lanjutan

Algoritma	Masalah	Rekurens	Kompleksitas	Catatan
Closest Pair	Geometri komputasi	2T(n/2)+n	O(n log n)	Bandingkan strip terbatas
Karatsuba	Perkalian integer	3T(n/2)+n	O(n^1.585)	3 perkalian rekursif
BFPRT	Seleksi median	T(n/5)+T(7n/10+6)+n	O(n)	Worst-case linear
FFT	Polinomial / sinyal	2T(n/2)+n	O(n log n)	Even–odd decomposition

2

Algoritma O(n log n)

1

Algoritma O(n)

1

Algoritma sub-kuadratik

4

Contoh lanjutan inti

Penutup

Dari Paradigma ke Strategi Tingkat Lanjut

Materi lanjutan Divide and Conquer menunjukkan bahwa satu paradigma bisa melahirkan solusi efisien pada domain yang sangat berbeda: geometri, aritmetika besar, seleksi deterministik, hingga transformasi sinyal.

📌

Konsep

Pecah masalah dengan struktur yang tepat.

🧮

Analisis

Pilih teknik penyelesaian rekurens yang sesuai.

🌍

Aplikasi

Gunakan D&C pada masalah nyata, bukan hanya sorting.

Algoritma Divide and ConquerLanjutan