Pengenalan Kompleksitas

Sebuah algoritma yang berjalan 1 detik pada 100 elemen data bisa memerlukan berjam-jam, atau bahkan berabad-abad, saat data membengkak menjadi 100 juta elemen. Tanpa analisis kompleksitas, kita tidak punya cara sistematis untuk memprediksi perilaku tersebut sebelum kode benar-benar dijalankan. Pada Chapter ini kita akan memperkenalkan konsep kompleksitas sebagai alat untuk berbicara tentang efisiensi algoritma secara mandiri dari mesin, compiler, maupun bahasa pemrograman. Kompleksitas memungkinkan kita membandingkan dua algoritma secara adil sebelum menulis satu baris kode pun.

Mengapa Kompleksitas Diperlukan #

Misalkan kita memiliki dua implementasi linear search — satu ditulis dengan C++ dan satu lagi dengan Python. Berdasarkan pengukuran wall-clock, versi C++ biasanya lebih cepat. Apakah kesimpulan yang benar kemudian menjadi “C++ lebih efisien untuk pencarian”? Tidak. Kedua implementasi sebenarnya melakukan jumlah operasi yang setara: kira-kira n kali pembandingan pada array berukuran n. Pengukuran waktu konkret sangat bergantung pada hardware, compiler, dan optimasi yang aktif, sehingga tidak dapat dipakai sebagai dasar pembanding yang adil.

Kompleksitas algoritma adalah cara mengukur jumlah operasi atau jumlah memori yang dipakai algoritma sebagai fungsi dari ukuran input n. Dengan fokus pada jumlah operasi, kita memisahkan properti intrinsik algoritma dari properti environment tempat algoritma dijalankan.

Aspek	Pengukuran Waktu Konkret	Analisis Kompleksitas
Bergantung pada hardware	Ya	Tidak
Bergantung pada compiler	Ya	Tidak
Bisa diprediksi sebelum kode dijalankan	Tidak	Ya
Bisa membandingkan algoritma berbeda secara adil	Sulit	Ya
Menggunakan satuan absolut	Detik, milidetik	Fungsi `f(n)`

Dua Dimensi Kompleksitas #

Kompleksitas algoritma diukur pada dua dimensi yang biasanya saling berkaitan:

Time complexity — berapa banyak operasi (langkah komputasi) yang dilakukan algoritma sebagai fungsi dari n.
Space complexity — berapa banyak memori tambahan yang dialokasikan algoritma sebagai fungsi dari n.

Sebagai contoh, algoritma merge sort memiliki time complexity O(n log n) dan space complexity O(n) karena memerlukan array bantu seukuran input. Sebaliknya, heap sort memiliki time complexity O(n log n) dan space complexity O(1) karena melakukan pengurutan secara in-place.

flowchart TD A[Ukuran Input n] --> B[Time Complexity] A --> C[Space Complexity] B --> D["Berapa langkah?"] C --> E["Berapa memori tambahan?"]

Apa yang Dimaksud dengan “Ukuran Input” #

Ukuran input n tidak selalu berarti jumlah elemen array. Tergantung pada masalah yang dihadapi, n bisa berarti:

Jumlah elemen pada struktur data (sorting, searching).
Jumlah simpul pada graph (traversal BFS/DFS).
Panjang string (string matching).
Jumlah bit pada representasi bilangan (algoritma aritmetika besar).
Jumlah baris pada matriks (algoritma matriks).

Eksperimen: Menghitung Operasi Secara Eksplisit #

Untuk memahami konsep kompleksitas secara konkret, kita akan menulis sebuah fungsi yang menghitung jumlah operasi yang dilakukan dua algoritma berbeda pada masalah yang sama: mencari nilai maksimum pada array. Algoritma pertama melakukan satu kali pass, algoritma kedua melakukan dua kali pass (satu untuk mencari nilai maksimum, satu lagi untuk memastikan keunikannya).

Mekanisme: Mengapa Dua Pass Lebih Lambat #

Algoritma satu pass menjelajah array satu kali, melakukan satu pembandingan per elemen. Algoritma dua pass menjelajah array dua kali: pass pertama mencari maksimum, pass kedua menghitung berapa kali nilai maksimum muncul. Total operasi pembandingan menjadi 2n, dua kali lipat algoritma pertama. Meskipun konstanta 2 tampak kecil, prinsip “banyak pass = banyak operasi” menjadi dasar banyak optimasi DSA.

Kode Program #

cpp
#include <iostream>
#include <vector>

// Algoritma 1: satu pass, hitung operasi pembandingan
int maxSatuPass(const std::vector<int>& v, long long& op) {
    op = 0;
    int maks = v[0];
    for (std::size_t i = 1; i < v.size(); ++i) {
        ++op;                       // satu pembandingan
        if (v[i] > maks) {
            maks = v[i];
        }
    }
    return maks;
}

// Algoritma 2: dua pass, pass pertama mencari maksimum,
// pass kedua menghitung frekuensi nilai maksimum
int maxDuaPass(const std::vector<int>& v, long long& op) {
    op = 0;
    int maks = v[0];
    for (std::size_t i = 1; i < v.size(); ++i) {
        ++op;
        if (v[i] > maks) maks = v[i];
    }
    int frek = 0;
    for (int x : v) {
        ++op;
        if (x == maks) ++frek;
    }
    (void)frek;                    // dipakai hanya untuk demonstrasi
    return maks;
}

int main() {
    std::vector<int> data{3, 1, 4, 1, 5, 9, 2, 6, 5, 3};

    long long op1 = 0, op2 = 0;
    int m1 = maxSatuPass(data, op1);
    int m2 = maxDuaPass(data, op2);

    std::cout << "Maks (1 pass) = " << m1 << ", operasi = " << op1 << '\n';
    std::cout << "Maks (2 pass) = " << m2 << ", operasi = " << op2 << '\n';
    return 0;
}

Output yang Dihasilkan:

text

Maks (1 pass) = 9, operasi = 9
Maks (2 pass) = 9, operasi = 19

Bedah Kode Baris-per-Baris #

Mari kita telaah bagian-bagian penting program di atas:

Baris long long& op: parameter output reference untuk mengembalikan jumlah operasi. Kita pakai long long agar tidak overflow saat n sangat besar.
Baris int maks = v[0];: inisialisasi awal dengan elemen pertama. Kita tidak memakai INT_MIN agar tidak perlu header <climits> dan tetap berlaku untuk semua tipe data yang memiliki operator >.
Baris ++op; sebelum pembandingan: kita menambah penghitung operasi tepat sebelum pembandingan v[i] > maks. Inilah “satuan operasi” yang menjadi dasar perhitungan kompleksitas.
Baris for (int x : v): range-based for loop yang menjelajah seluruh elemen array untuk pass kedua.
Baris (void)frek;: ekspresi ini mencegah warning unused variable dari compiler. Variabel frek memang hanya dihitung untuk menambah op.
Baris di main: kita membuat array 10 elemen. Output menunjukkan algoritma satu pass melakukan 9 pembandingan (n-1), sedangkan algoritma dua pass melakukan 19 pembandingan (9 untuk pass pertama + 10 untuk pass kedua). Selisih ini akan semakin besar seiring n tumbuh.

Skala Pertumbuhan: Glimpse Awal #

Tanpa mendefinisikan formalisme Big-O terlebih dahulu, kita bisa melihat pola pertumbuhan jumlah operasi saat n membesar. Tabel berikut menunjukkan beberapa fungsi kompleksitas umum dan nilai operasinya pada beberapa ukuran input.

Fungsi `f(n)`	n=10	n=100	n=1.000	n=10.000
`1`	1	1	1	1
`log n`	3	7	10	13
`n`	10	100	1.000	10.000
`n log n`	33	664	9.966	132.877
`n²`	100	10.000	1.000.000	100.000.000
`2ⁿ`	1.024	≈10³⁰	≈10³⁰¹	≈10³⁰¹⁰

Perhatikan bahwa 2ⁿ meledak sangat cepat — pada n=100 nilainya sudah jauh melebihi jumlah atom di alam semesta. Inilah mengapa algoritma exponential hanya praktis untuk input sangat kecil.

Ringkasan #

Kompleksitas adalah cara mengukur efisiensi algoritma sebagai fungsi dari ukuran input n, terlepas dari hardware dan compiler.
Dua dimensi utama: time complexity (jumlah operasi) dan space complexity (jumlah memori tambahan).
Ukuran input n harus didefinisikan jelas: bisa jumlah elemen, simpul, bit, atau baris.
Dua algoritma yang menghasilkan output sama bisa memiliki jumlah operasi sangat berbeda, seperti contoh satu pass vs dua pass pada pencarian maksimum.

Pada Chapter berikutnya kita akan mendalami time complexity secara lebih formal, termasuk cara menghitung jumlah operasi pada loop, fungsi rekursif, dan struktur kontrol lainnya.