Matdis — Bab 11
Kompleksitas Algoritma
Bahasa formal untuk mengukur efisiensi: notasi asimptotik, analisis kasus, master theorem, dan kelas P/NP.
Ref: Rinaldi Munir, Matematika Diskrit, Edisi 7 (2020), Bab 11. — CLRS, Introduction to Algorithms, 4th ed., Ch. 3–4. — Sipser, Introduction to the Theory of Computation, 3rd ed., Ch. 7.
Mengapa Kompleksitas Itu Penting?
Analogi: dua orang sama-sama sampai tujuan, tapi yang satu jalan kaki dan yang satu naik kereta. Kompleksitas algoritma adalah cara mengukur "moda transportasi" sebuah program — bukan berapa detik ia berjalan di laptop Anda, melainkan bagaimana waktunya tumbuh ketika datanya membesar.
Bedanya dramatis. Algoritma O(n log n) menyortir 1 juta data dalam hitungan detik. Algoritma O(n²) untuk data yang sama butuh berjam-jam. Dan algoritma O(2ⁿ) pada n=100 tidak akan pernah selesai — bahkan jika seluruh komputer di dunia dijalankan sampai matahari padam.
Karena itu pertanyaan "apakah masalah ini punya algoritma polinomial?" jadi sangat penting, dan melahirkan kelas P, NP, dan NP-complete yang dibahas di bab ini.
1. Notasi Asimptotik
Big-O (Batas Atas)
f(n) = O(g(n)) jika ada konstanta c > 0 dan n₀ sehingga:
0 ≤ f(n) ≤ c·g(n) untuk n ≥ n₀
g(n) = batas atas asimptotik. "f tumbuh tidak lebih cepat dari g."
Big-Omega & Big-Theta
Ω(g): batas bawah. f(n) ≥ c·g(n) untuk n ≥ n₀.
Θ(g): batas ketat. f = O(g) DAN f = Ω(g).
o(g): strictly O. lim f/g = 0 saat n→∞.
ω(g): strictly Ω. lim g/f = 0 saat n→∞.
Aturan Aljabar Big-O
1. Konstanta diabaikan: O(5n) = O(n).
2. Ambil suku dominan: O(n³ + n² + 100n + 1) = O(n³).
3. Penjumlahan: O(f) + O(g) = O(max(f, g)).
4. Perkalian (loop bersarang): O(f) · O(g) = O(f·g).
5. Logaritma basis tidak relevan: O(log₂ n) = O(log₁₀ n) = O(ln n).
6. Hierarki: O(1) ⊂ O(log n) ⊂ O(n) ⊂ O(n log n) ⊂ O(n²) ⊂ O(2ⁿ) ⊂ O(n!).
Visualisasi: Pertumbuhan Fungsi Kompleksitas
Animasi garis O(2ⁿ) menunjukkan pertumbuhan eksplosif. Untuk n=80: 2⁸⁰ ≈ 10²⁴ operasi — secara praktis tak terbatas.
2. Big-O Explorer Interaktif
Berapa operasi untuk n = ?
O(1)
1
O(log n)
4.32
O(n)
20
O(n log n)
86.44
O(n²)
400
O(n³)
8,000
O(2ⁿ)
1.0M
O(n!)
∞ (overflow)
Coba n=50: O(2ⁿ) = 2⁵⁰ ≈ 10¹⁵. Bahkan CPU 10GHz butuh >115 hari. Untuk kunci kriptografi n=128: 2¹²⁸ = ∞ secara praktis.
3. Analisis Best / Average / Worst Case
Best Case (Ω)
Input yang membuat algoritma berjalan tercepat. Dinyatakan dengan Ω.
Contoh: insertion sort O(n) jika input sudah hampir terurut.
Average Case (Θ)
Ekspektasi waktu atas distribusi input acak. Paling relevan untuk analisis praktis.
Quicksort: Θ(n log n) rata-rata (pivot selalu baik secara rata-rata).
Worst Case (O)
Input adversarial yang memaksa algoritma paling lambat. Garansi keamanan!
Kriptografi WAJIB menganalisis worst-case: penyerang selalu memilih input terburuk.
4. Kompleksitas Algoritma Standar
Pilih Algoritma untuk Detail:
Best
O(n log n)
Average
O(n log n)
Worst
O(n log n)
Space
O(n)
Stabil?
Ya
Divide-and-conquer deterministik. Stabil, konsisten. Standar untuk external sort dan parallel sort.
Tabel Kompleksitas Lengkap
| Algoritma | Best | Average | Worst | Space | Stabil |
|---|---|---|---|---|---|
| Bubble Sort | O(n) | O(n²) | O(n²) | O(1) | Ya |
| Insertion Sort | O(n) | O(n²) | O(n²) | O(1) | Ya |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Ya |
| Quick Sort | O(n log n) | O(n log n) | O(n²) | O(log n) | Tidak |
| Heap Sort | O(n log n) | O(n log n) | O(n log n) | O(1) | Tidak |
| Binary Search | O(1) | O(log n) | O(log n) | O(1) | - |
| BFS / DFS Graf | - | O(V+E) | O(V+E) | O(V) | - |
| Dijkstra (heap) | - | O((V+E)log V) | O((V+E)log V) | O(V) | - |
5. Master Theorem
Master Theorem (CLRS 4th ed.)
Untuk T(n) = aT(n/b) + f(n) dengan a ≥ 1, b > 1:
Hitung: n^(log_b a) = n^(log_b a)
Case 1: f(n) = O(n^(log_b a - ε)) → T(n) = Θ(n^(log_b a))
Case 2: f(n) = Θ(n^(log_b a)) → T(n) = Θ(n^(log_b a) log n)
Case 3: f(n) = Ω(n^(log_b a + ε)) → T(n) = Θ(f(n))
Kalkulator Master Theorem: T(n) = aT(n/b) + Θ(nᵈ)
n^(log_b a) = n^(1.000)
Case 2: f(n)=Θ(n^1) sama pertumbuhannya dengan n^log_b(a)
T(n) = Θ(n^1 log n)
6. Kelas Kompleksitas: P, NP, NP-Complete, NP-Hard
Hierarki Kelas Kompleksitas (Asumsi P ≠ NP)
Eksplorasi Masalah: Kelas Kompleksitas & Aplikasinya
Mengurutkan n elemen
Verifikasi solusi: O(n)
Aplikasi Nyata
Merge sort O(n log n) dipakai hampir di semua basis data untuk ORDER BY dan untuk mempercepat operasi JOIN.
7. Contoh Soal & Pembahasan
Soal 1: Identifikasi Big-O
Tentukan Big-O dari T(n) = 5n³ + 3n² + 100n + log n + 1000.
Soal 2: Analisis Loop Bersarang
Berapa kompleksitas: for i in 1..n: for j in i..n: print(i,j)?
Soal 3: Pembuktian Big-O
Buktikan secara formal: 3n² + 5n + 7 = O(n²).
Soal 4: Master Theorem — Merge Sort
Selesaikan T(n) = 2T(n/2) + n (Merge Sort recurrence).
Soal 5: Master Theorem — Strassen
Algoritma Strassen: T(n) = 7T(n/2) + O(n²). Tentukan kompleksitasnya.
Soal 6: Reduksi Polinomial
Diketahui 3-SAT adalah NP-complete. Jelaskan bagaimana membuktikan bahwa Pewarnaan Graf dengan 3 warna (3-Coloring) juga NP-complete.
Penerapan di Dunia Nyata
Basis Data & Indeks: Pencarian tanpa indeks adalah O(n) — memindai seluruh tabel. Dengan indeks B-Tree menjadi O(log n). Pada tabel 1 miliar baris, itu selisih antara 1 miliar operasi dan sekitar 30 operasi. Inilah alasan setiap DBMS punya indeks.
Kompilator: Alokasi register dimodelkan sebagai pewarnaan graf (NP-complete). Karena kompilator tidak boleh berjalan berjam-jam, ia memakai heuristik pewarnaan, bukan solusi optimal.
Logistik & Penjadwalan: Rute pengiriman adalah TSP, penjadwalan ujian adalah pewarnaan graf. Keduanya NP-complete, sehingga industri memakai algoritma aproksimasi yang menjamin hasil "cukup baik" dalam waktu polinomial.
Batas Praktis: Aturan praktis — O(n log n) skala ke miliaran data, O(n²) sampai puluhan ribu, O(2ⁿ) mentok di n ≈ 40-80. Mengetahui kelas kompleksitas program Anda memberi tahu ukuran data maksimum yang realistis sebelum Anda menulis kodenya.
Bank Soal Multi-Kompleksitas & Kasus Terintegrasi
Ref: Munir, R. (2020). Matematika Diskrit, Edisi 7, Bab 11.
Mudah
1. Urutkan dari tercepat ke terlambat: O(n!), O(2ⁿ), O(n³), O(n log n), O(log n), O(1).
2. Apakah f(n)=5n² + 3n + 7 adalah O(n²)? Buktikan dengan definisi.
3. Berapa kompleksitas waktu algoritma binary search? Jelaskan mengapa O(log n).
4. Apa perbedaan P dan NP? Apakah setiap masalah yang solusinya bisa diverifikasi cepat juga bisa diselesaikan cepat?
Sedang
1. Terapkan Master Theorem ke T(n)=3T(n/4)+n log n.
2. Tunjukkan bahwa Vertex Cover ∈ NP dengan mendefinisikan verifier polinomialnya.
3. Jelaskan mengapa Merge Sort lebih disukai dari Quick Sort untuk dataset besar di memori eksternal.
4. Algoritma manakah lebih efisien untuk mencari GCD: Naif (pembagian trial) atau Euclidean? Analisis kompleksitasnya.
Sulit
1. Buktikan: 3-SAT ≤_p Independent Set (IS). Artinya, 3-SAT dapat direduksi ke IS dalam waktu polinomial. Konstruksi reduksi dan kebenaran.
2. Terapkan Master Theorem ke rekurensi Merge Sort T(n)=2T(n/2)+n dan buktikan secara penuh menggunakan substitusi.
3. Algoritma Knapsack 0/1 dengan pemrograman dinamis berjalan dalam O(nW), dengan n = jumlah barang dan W = kapasitas. Mengapa ini tidak membuktikan P = NP, padahal Knapsack adalah NP-complete?
Kasus Terintegrasi (2+ Topik)
Tunjukkan bahwa jika SAT ∈ P maka P=NP. Gunakan fakta SAT adalah NP-complete (Cook-Levin theorem) dan definisi NP-completeness untuk deduksi lengkap.
Analisis kompleksitas FFT (Fast Fourier Transform): T(n) = 2T(n/2) + O(n). Bandingkan dengan perkalian polinom cara naif O(n²). Hitung speedup untuk n = 1024 koefisien.
Jelaskan rantai reduksi klasik: 3-SAT ≤ₚ Clique ≤ₚ Vertex Cover ≤ₚ Himpunan Dominasi. Apa arti setiap tanda panah, dan apa kesimpulannya tentang keempat masalah tersebut?