Setiap program menanggung dua biaya yang saling berkaitan: waktu komputasi dan penggunaan memori. Sebuah algoritma yang bekerja benar tetapi memerlukan seratus juta operasi untuk data yang sebenarnya kecil akan terasa lambat begitu data membesar, sedangkan algoritma yang cepat bisa gagal dijalankan bila membutuhkan memori lebih besar daripada yang tersedia. Kompleksitas adalah cara kita menilai kedua biaya tersebut sebagai fungsi dari ukuran masalah, yang biasanya dilambangkan dengan n. Chapter ini melatih kebiasaan paling mendasar dalam ilmu komputer: menghitung berapa banyak pekerjaan yang benar-benar dilakukan kode kita, bukan sekadar melihatnya berjalan.

Biaya Komputasi sebagai Fungsi Ukuran Input #

Ukuran masalah n bisa berupa jumlah elemen pada array, jumlah node pada tree, atau panjang sebuah string. Yang perlu ditegaskan sejak awal: waktu dalam detik bergantung pada mesin, tetapi jumlah operasi tidak. Program yang sama dijalankan di laptop lama dan server baru akan menghasilkan durasi berbeda, sementara jumlah perbandingan dan penjumlahan yang dikerjakannya persis sama. Karena itu kita menilai algoritma dengan menghitung operasi sebagai fungsi dari n, lalu menyebut pola pertumbuhannya — inilah yang nantinya diringkas oleh Big-O notation pada chapter berikutnya.

Cara paling sederhana untuk melihat biaya sebuah fungsi adalah memberi pencatat: satu variabel counter yang bertambah setiap kali badan perulangan dieksekusi. Pendekatan ini deterministik, sehingga hasilnya bisa kita verifikasi persis seperti pada program berikut:

cpp 
// Menghitung jumlah operasi nyata untuk tiga bentuk algoritma.
// Pendekatan ini deterministik: jumlah operasi tidak berubah antar mesin.
#include <iostream>

// Biaya linear: 1 operasi per elemen, total tumbuh sebanding dengan n
long long hitungOperasiLinear(int n) {
    long long operasi = 0;
    long long total = 0;
    for (int i = 1; i <= n; ++i) {
        total += i;      // pekerjaan inti per iterasi
        ++operasi;       // pencatat jumlah iterasi
    }
    return operasi;
}

// Biaya kuadrat: perulangan di dalam perulangan, total n * n operasi
long long hitungOperasiKuadrat(int n) {
    long long operasi = 0;
    long long total = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            total += static_cast<long long>(i) * j;
            ++operasi;
        }
    }
    return operasi;
}

// Biaya logaritmik: masalah dibagi dua setiap langkah
long long hitungOperasiLogaritmik(int n) {
    long long operasi = 0;
    while (n > 1) {
        n /= 2;
        ++operasi;
    }
    return operasi;
}

int main() {
    int daftarN[] = {10, 100, 1000, 10000};
    std::cout << "n     | O(n)   | O(n^2)    | O(log n)\n";
    for (int n : daftarN) {
        std::cout << n << " | " << hitungOperasiLinear(n)
                  << " | " << hitungOperasiKuadrat(n)
                  << " | " << hitungOperasiLogaritmik(n) << '\n';
    }

    // Kompleksitas memori: ukuran data dapat dihitung dari sizeof
    std::cout << "sizeof(int) = " << sizeof(int) << " byte\n";
    std::cout << "1 juta int       = " << 1000000LL * sizeof(int) << " byte\n";
    std::cout << "1 juta long long = " << 1000000LL * sizeof(long long) << " byte\n";
    return 0;
}

Output yang Dihasilkan:

text 
n     | O(n)   | O(n^2)    | O(log n)
10 | 10 | 100 | 3
100 | 100 | 10000 | 6
1000 | 1000 | 1000000 | 9
10000 | 10000 | 100000000 | 13
sizeof(int) = 4 byte
1 juta int       = 4000000 byte
1 juta long long = 8000000 byte

Bedah baris penting:

  1. Baris 6-14 (hitungOperasiLinear): perulangan menjalankan badan persis n kali, sehingga pencatat mengembalikan n apa pun isi pekerjaannya. Ini pola biaya linear.
  2. Baris 17-27 (hitungOperasiKuadrat): perulangan bagian dalam dieksekusi n kali untuk setiap iterasi perulangan luar, sehingga totalnya n * n. Menambah n sepuluh kali lipat membuat operasi membesar seratus kali lipat.
  3. Baris 30-37 (hitungOperasiLogaritmik): n dibagi dua setiap langkah sampai tersisa 1, sehingga jumlah langkah kira-kira log₂ n. Untuk n = 10000 cukup 13 langkah — inilah alasan pencarian biner sangat cepat.
  4. Baris 41-46: tabel di main() membandingkan ketiga fungsi pada nilai n yang sama, sehingga perbedaan pertumbuhannya terlihat langsung.
  5. Baris 49-51: sizeof(int) adalah 4 byte di platform ini, jadi satu juta int menempati 4.000.000 byte — biaya memori ikut tumbuh linear terhadap jumlah elemen.

Mengukur Waktu Nyata dengan std::chrono #

Selain menghitung operasi, C++ menyediakan cara mengukur durasi nyata lewat header <chrono>. Polanya tiga langkah: catat titik waktu sebelum, jalankan pekerjaan, catat titik waktu sesudah, lalu hitung selisihnya. Karena angka durasi bergantung pada mesin dan beban sistem, hasilnya berubah antar eksekusi — berbeda dengan jumlah operasi yang selalu tetap:

cpp Pola pengukuran waktu dengan std::chrono (durasi keluaran bervariasi antar mesin) 
#include <chrono>
#include <iostream>

int main() {
    auto mulai = std::chrono::steady_clock::now();
    long long total = 0;
    for (int i = 0; i < 100000000; ++i) {
        total += i;
    }
    auto selesai = std::chrono::steady_clock::now();
    auto durasi =
        std::chrono::duration_cast<std::chrono::milliseconds>(selesai - mulai);
    std::cout << "Loop selesai dalam " << durasi.count() << " ms\n";
    return 0;
}

Pola di atas layak dipakai untuk perbandingan kasar di mesin yang sama: jalankan kedua algoritma pada data yang identik, lalu bandingkan durasinya. Untuk pembelajaran konsep, jumlah operasi lebih dapat diandalkan karena sifatnya deterministik — dua run selalu menghasilkan angka yang sama persis. Di chapter-chapter berikutnya kita akan sering menampilkan jumlah operasi atau jumlah perbandingan sebagai bukti perbedaan kompleksitas, dan menyisakan pengukuran waktu untuk eksperimen Anda sendiri.

Kompleksitas Memori #

Kompleksitas memori dihitung dengan pola yang sama, tetapi unitnya adalah byte atau jumlah elemen. Array berisi n buah int memakai sekitar 4n byte karena setiap int berukuran 4 byte; satu juta elemen berarti 4 MB, dan long long menggandakannya menjadi 8 MB. Struktur data berbasis node seperti linked list menghabiskan lebih banyak memori daripada angka ini karena setiap node membawa pointer tambahan, sebuah biaya yang akan kita hitung konkret pada chapter Linked List.

Kebiasaan membaca biaya dari struktur kode — satu perulangan berarti linear, bersarang berarti kuadrat, membagi dua berarti logaritmik — adalah fondasi seluruh section ini. Chapter berikutnya memberi notasi resmi untuk pola-pola tersebut: Big-O notation, sehingga kita bisa menulis O(n), O(n log n), atau O(n²) tanpa menunjukkan tabel angka setiap kali.

Rujukan resmi: std::chrono dan sizeof operator .