Membandingkan Kompleksitas

Setelah mempelajari notasi Big-O, Big-Omega, Big-Theta, analisis loop, rekursi, dan amortisasi, kita kini memiliki perangkat lengkap untuk membicarakan kompleksitas algoritma. Chapter ini merangkum kelas kompleksitas yang umum dijumpai di DSA, menyajikan tabel referensi komprehensif kompleksitas algoritma-algoritma klasik, dan menjelaskan metodologi untuk membandingkan dua algoritma secara sistematis. Tabel-tabel di sini akan menjadi rujukan cepat dalam sisa Course ini.

Hierarki Kompleksitas #

Berikut hierarki kelas kompleksitas dari paling cepat ke paling lambat, beserta contoh algoritma untuk masing-masing kelas:

flowchart LR A["O(1)"] --> B["O(log n)"] B --> C["O(sqrt n)"] C --> D["O(n)"] D --> E["O(n log n)"] E --> F["O(n^2)"] F --> G["O(n^3)"] G --> H["O(2^n)"] H --> I["O(n!)"]

Tabel Pertumbuhan Fungsi #

Tabel berikut menunjukkan nilai numerik untuk berbagai fungsi kompleksitas pada ukuran input berbeda. Gunakan tabel ini untuk memperoleh intuisi tentang skala pertumbuhan.

Fungsi `f(n)`	n=1	n=10	n=100	n=1.000	n=10.000	n=100.000
`1`	1	1	1	1	1	1
`log₂ n`	0	3,3	6,6	10,0	13,3	16,6
`√n`	1,0	3,2	10,0	31,6	100,0	316,2
`n`	1	10	100	1.000	10.000	100.000
`n log₂ n`	0	33	664	9.966	132.877	1.660.964
`n²`	1	100	10.000	10⁶	10⁸	10¹⁰
`n³`	1	1.000	10⁶	10⁹	10¹²	10¹⁵
`2ⁿ`	2	1.024	≈10³⁰	≈10³⁰¹	≈10³⁰¹⁰	—
`n!`	1	3,6×10⁶	≈9,3×10¹⁵⁷	—	—	—

Kompleksitas Algoritma Searching #

Algoritma	Best	Average	Worst	Space
Linear search	`O(1)`	`O(n)`	`O(n)`	`O(1)`
Binary search (iteratif)	`O(1)`	`O(log n)`	`O(log n)`	`O(1)`
Binary search (rekursif)	`O(1)`	`O(log n)`	`O(log n)`	`O(log n)`
Interpolation search	`O(log log n)`	`O(log log n)`	`O(n)`	`O(1)`
Exponential search	`O(1)`	`O(log n)`	`O(log n)`	`O(1)`
Ternary search	`O(1)`	`O(log₃ n)`	`O(log₃ n)`	`O(1)`
Jump search	`O(1)`	`O(√n)`	`O(√n)`	`O(1)`

Kompleksitas Algoritma Sorting #

Algoritma	Best	Average	Worst	Space	Stable
Bubble sort	`O(n)`	`O(n²)`	`O(n²)`	`O(1)`	Ya
Selection sort	`O(n²)`	`O(n²)`	`O(n²)`	`O(1)`	Tidak
Insertion sort	`O(n)`	`O(n²)`	`O(n²)`	`O(1)`	Ya
Shell sort	`O(n log n)`	`O(n^1.25)`	`O(n²)`	`O(1)`	Tidak
Merge sort	`O(n log n)`	`O(n log n)`	`O(n log n)`	`O(n)`	Ya
Quick sort (random pivot)	`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
Counting sort	`O(n + k)`	`O(n + k)`	`O(n + k)`	`O(n + k)`	Ya
Radix sort	`O(d·(n + k))`	`O(d·(n + k))`	`O(d·(n + k))`	`O(n + k)`	Ya
Bucket sort	`O(n + k)`	`O(n + k)`	`O(n²)`	`O(n + k)`	Ya

Kompleksitas Struktur Data #

Struktur Data	Access	Search	Insert	Delete	Space
Array statis	`O(1)`	`O(n)`	`O(n)`	`O(n)`	`O(n)`
`std::vector` (dinamis)	`O(1)`	`O(n)`	`O(1)` amortized	`O(n)`	`O(n)`
Singly linked list	`O(n)`	`O(n)`	`O(1)` (di kepala)	`O(1)` (di kepala)	`O(n)`
Doubly linked list	`O(n)`	`O(n)`	`O(1)` (di ujung)	`O(1)` (di ujung)	`O(n)`
Stack (array)	—	—	`O(1)`	`O(1)`	`O(n)`
Queue (array)	—	—	`O(1)`	`O(1)`	`O(n)`
Hash table ( chaining)	—	`O(1)` avg / `O(n)` worst	`O(1)` avg	`O(1)` avg	`O(n)`
Binary search tree (balanced)	`O(log n)`	`O(log n)`	`O(log n)`	`O(log n)`	`O(n)`
Binary search tree (unbalanced)	`O(n)`	`O(n)`	`O(n)`	`O(n)`	`O(n)`
AVL tree / Red-Black tree	`O(log n)`	`O(log n)`	`O(log n)`	`O(log n)`	`O(n)`
Heap (binary)	`O(1)` (peek)	`O(n)`	`O(log n)`	`O(log n)`	`O(n)`
Trie	`O(L)`	`O(L)`	`O(L)`	`O(L)`	`O(Σ·L)`

Kompleksitas Algoritma Graph #

Algoritma	Time Complexity	Space
BFS (adjacency list)	`O(V + E)`	`O(V)`
DFS (adjacency list)	`O(V + E)`	`O(V)`
BFS (adjacency matrix)	`O(V²)`	`O(V)`
DFS (adjacency matrix)	`O(V²)`	`O(V)`
Dijkstra (binary heap)	`O((V + E) log V)`	`O(V)`
Dijkstra (Fibonacci heap)	`O(E + V log V)`	`O(V)`
Bellman-Ford	`O(V · E)`	`O(V)`
Floyd-Warshall	`O(V³)`	`O(V²)`
Kruskal (sort + DSU)	`O(E log E)`	`O(V + E)`
Prim (binary heap)	`O(E log V)`	`O(V)`
Topological sort (DFS)	`O(V + E)`	`O(V)`
Tarjan SCC	`O(V + E)`	`O(V)`
Ford-Fulkerson (Edmonds-Karp)	`O(V · E²)`	`O(V + E)`

Kompleksitas Algoritma String #

Algoritma	Time	Preprocess	Space
Naive string match	`O(n·m)`	—	`O(1)`
Rabin-Karp	`O(n+m)` avg / `O(n·m)` worst	`O(m)`	`O(1)`
KMP (Knuth-Morris-Pratt)	`O(n + m)`	`O(m)`	`O(m)`
Z-algorithm	`O(n + m)`	`O(n + m)`	`O(n + m)`
Aho-Corasick	`O(n + m + z)`	`O(m · Σ)`	`O(m · Σ)`
Suffix array (DC3)	`O(n)`	—	`O(n)`
Suffix array (sort-based)	`O(n log n)`	—	`O(n)`
Suffix tree (Ukkonen)	`O(n)`	—	`O(n)`

Metodologi Membandingkan Dua Algoritma #

Saat dihadapkan pada dua algoritma yang menyelesaikan masalah yang sama, kita perlu metodologi sistematis untuk memilih. Berikut langkah-langkah yang dianjurkan:

1. Bandingkan Asimptotik (Big-Theta) #

Mulai dari kelas asimptotik. Bila A = Θ(n log n) dan B = Θ(n²), maka A menang untuk n besar tanpa syarat. Bila keduanya sama kelasnya, lanjut ke langkah berikutnya.

2. Bandingkan Konstanta (Empiris atau Teoritis) #

Bila kedua algoritma Θ(n log n), konstanta menjadi pembeda. Contoh: merge sort vs heap sort keduanya Θ(n log n), tetapi merge sort biasanya lebih cepat di praktik karena akses memori lebih sekuensial.

3. Pertimbangkan Kasus Spesial #

Beberapa algoritma unggul pada input tertentu: insertion sort cepat pada array hampir terurut (Θ(n)); binary search cepat pada array terurut (Θ(log n)); counting sort cepat bila rentang nilai kecil (Θ(n + k)).

4. Faktor Memori #

Pada perangkat dengan RAM terbatas, algoritma in-place seperti heap sort menjadi pilihan meski sedikit lebih lambat.

5. Benchmark Konkret #

Setelah analisis asimptotik, uji dengan data realistis. Profiling mengungkap efek cache, branch prediction, dan overhead yang tidak terlihat dalam analisis.

Kode: Membandingkan Bubble vs Insertion Sort pada Array Hampir Terurut #

cpp
#include <iostream>
#include <vector>
#include <chrono>

long long cmpBubble = 0, cmpInsert = 0;

void bubbleSort(std::vector<int>& v) {
    cmpBubble = 0;
    int n = static_cast<int>(v.size());
    for (int i = 0; i < n - 1; ++i) {
        bool tukar = false;
        for (int j = 0; j < n - i - 1; ++j) {
            ++cmpBubble;
            if (v[j] > v[j + 1]) {
                std::swap(v[j], v[j + 1]);
                tukar = true;
            }
        }
        if (!tukar) break;
    }
}

void insertionSort(std::vector<int>& v) {
    cmpInsert = 0;
    for (std::size_t i = 1; i < v.size(); ++i) {
        int key = v[i];
        int j = static_cast<int>(i) - 1;
        while (j >= 0) {
            ++cmpInsert;
            if (v[j] > key) { v[j + 1] = v[j]; --j; }
            else break;
        }
        v[j + 1] = key;
    }
}

int main() {
    // Array hampir terurut: 95% terurut, 5% acak
    std::vector<int> a = {1, 2, 3, 4, 5, 6, 7, 8, 12, 10, 11, 9, 13, 14, 15};
    auto b = a;

    bubbleSort(a);
    insertionSort(b);

    std::cout << "Array 15 elemen, hampir terurut\n";
    std::cout << "Bubble sort    : " << cmpBubble << " pembandingan\n";
    std::cout << "Insertion sort : " << cmpInsert << " pembandingan\n";
    return 0;
}

Output yang Dihasilkan:

text
Array 15 elemen, hampir terurut
Bubble sort    : 50 pembandingan
Insertion sort : 19 pembandingan

Bedah Kode Baris-per-Baris #

Variabel cmpBubble dan cmpInsert: penghitung pembandingan global. Keduanya berkelas asimptotik sama (O(n²) worst), tetapi kita ingin melihat konstanta pada kasus hampir terurut.
Baris bool tukar = false;: optimasi early termination pada bubble sort. Bila satu pass tidak ada pertukaran, array sudah terurut.
Array {1, 2, 3, 4, 5, 6, 7, 8, 12, 10, 11, 9, 13, 14, 15}: array hampir terurut, hanya 3 elemen yang tidak pada posisi tepat.
Output: bubble sort memerlukan 50 pembandingan, insertion sort hanya 19. Selisih besar menunjukkan insertion sort unggul pada input hampir terurut, meskipun keduanya sama-sama Θ(n²) worst case.
Implikasi: meskipun kelas asimptotik sama, konstanta dan adaptasi terhadap input dapat memberi perbedaan dramatis. Inilah mengapa analisis kompleksitas perlu dilengkapi dengan uji empiris.

Aturan Praktis Memilih Algoritma #

Situasi	Algoritma yang Disarankan
`n` kecil (< 50)	Insertion sort, linear search
`n` sedang (50–10.000), tidak terurut	Quick sort, hash table
`n` besar (> 10.000), perlu stabil	Merge sort
`n` sangat besar, perlu in-place	Heap sort
Rentang nilai kecil (misal 0–255)	Counting sort
Data string panjang	Radix sort
Data terurut, perlu cari	Binary search
Data tidak terurut, perlu cari	Hash table
Update sering, query max/min	Heap
Konektivitas graph	Union-Find
Jarak terpendek, satu sumber	Dijkstra (non-negatif), Bellman-Ford (umum)
Jarak terpendek, semua pasang	Floyd-Warshall (V kecil), Johnson (V besar)

Ringkasan #

Hierarki kompleksitas: 1 < log n < √n < n < n log n < n² < n³ < 2ⁿ < n!.
Tabel referensi kompleksitas searching, sorting, struktur data, graph, dan string menyediakan rujukan cepat.
Saat membandingkan dua algoritma: mulai dari asimptotik, lalu konstanta, lalu kasus spesial, lalu faktor memori, lalu benchmark.
Tidak ada algoritma terbaik universal; pemilihan selalu melibatkan trade-off.

Pada Section berikutnya, analisis-dan-pembuktian-algoritma, kita akan beralih dari pertanyaan “seberapa cepat” ke pertanyaan “apakah benar”. Kita akan mempelajari loop invariant, induksi matematis, dan pembuktian kebenaran algoritma secara formal.