Big-O Notation

Pada chapter sebelumnya kita menghitung jumlah operasi secara manual dan melihat tiga pola pertumbuhan yang berbeda. Big-O notation adalah notasi baku untuk merangkum pola itu: ia menjawab pertanyaan “seberapa cepat biaya tumbuh ketika input membesar”, bukan “berapa milidetik program ini berjalan”. Dengan Big-O kita bisa membandingkan dua algoritma tanpa mempedulikan kecepatan mesin, dan bisa memprediksi apa yang terjadi saat data berlipat sepuluh kali. Chapter ini mengenalkan lima kelas Big-O yang paling sering ditemui, menunjukkan tabel angka nyata, lalu memberi aturan praktis menghitung Big-O langsung dari kode.

Lima Kelas Pertumbuhan yang Wajib Dikenali #

Tabel berikut merangkum kelas-kelas biaya yang akan kita temui berulang kali sepanjang section ini. Kolom “contoh” mengacu pada algoritma atau operasi yang akan kita implementasikan sendiri di chapter-chapter selanjutnya.

Urutannya penting: makin ke bawah, biaya tumbuh makin cepat terhadap n. Perbedaan yang tampak kecil pada n kecil menjadi jurang yang lebar pada data besar, dan itulah alasan pemilihan algoritma lebih menentukan daripada micro-optimization.

Tabel Pertumbuhan Angka Nyata #

Daripada mempercayai klaim di atas mentah-mentah, program berikut menghitung sendiri kelima nilai untuk berbagai n. Semua angka keluaran dihitung oleh program, sehingga tabelnya bisa diverifikasi ulang kapan pun:

// Tabel pertumbuhan: membandingkan nilai nyata lima kelas Big-O
// untuk n yang semakin besar. Semua nilai dihitung program, bukan dikira-kira.
#include <iostream>

// log2 dibulatkan ke bawah, dihitung dengan membagi dua sampai sisa 1
long long log2Bulat(int n) {
    long long hasil = 0;
    while (n > 1) {
        n /= 2;
        ++hasil;
    }
    return hasil;
}

int main() {
    std::cout << "n      | O(1) | O(log n) | O(n) | O(n log n) | O(n^2)\n";
    int daftarN[] = {10, 100, 1000, 10000, 100000, 1000000};
    for (int n : daftarN) {
        long long logN = log2Bulat(n);
        long long nLogN = static_cast<long long>(n) * logN;
        long long nKuadrat = static_cast<long long>(n) * n;
        std::cout << n << " | " << 1 << " | " << logN
                  << " | " << n << " | " << nLogN
                  << " | " << nKuadrat << '\n';
    }

    // Ilustrasi aturan: dua perulangan berurutan dijumlahkan,
    // perulangan bersarang dikalikan.
    int n = 1000;
    long long berurutan = n + n;          // O(n) + O(n)  -> O(n)
    long long bersarang = static_cast<long long>(n) * n;  // O(n) * O(n) -> O(n^2)
    std::cout << "Berurutan (n + n) untuk n=1000: " << berurutan << " operasi\n";
    std::cout << "Bersarang  (n * n) untuk n=1000: " << bersarang << " operasi\n";
    return 0;
}

Output yang Dihasilkan:

n      | O(1) | O(log n) | O(n) | O(n log n) | O(n^2)
10 | 1 | 3 | 10 | 30 | 100
100 | 1 | 6 | 100 | 600 | 10000
1000 | 1 | 9 | 1000 | 9000 | 1000000
10000 | 1 | 13 | 10000 | 130000 | 100000000
100000 | 1 | 16 | 100000 | 1600000 | 10000000000
1000000 | 1 | 19 | 1000000 | 19000000 | 1000000000000
Berurutan (n + n) untuk n=1000: 2000 operasi
Bersarang  (n * n) untuk n=1000: 1000000 operasi

Bedah baris penting:

1. Baris 6-12 (log2Bulat): menghitung ⌊log₂ n⌋ dengan membagi n dua sampai tersisa 1. Untuk n = 1.000.000 hasilnya 19 — membagi dua sangat cepat mengecilkan masalah.
2. Baris 18-26: untuk setiap n di daftar, program menghitung logN, nLogN, dan nKuadrat, lalu mencetak satu baris tabel. Semua perhitungan memakai long long agar n² untuk n = 1.000.000 (satu triliun) tetap muat.
3. Baris 30-31: baris komentar menegaskan aturan yang dibuktikan dua baris di bawahnya — operasi berurutan dijumlahkan, operasi bersarang dikalikan.
4. Baris 32-33: untuk n = 1000, perulangan berurutan butuh 2000 operasi sedangkan yang bersarang butuh 1.000.000 — perbedaan 500 kali lipat hanya karena satu tingkat perulangan tambahan.

Perhatikan kolom O(n²): ketika n naik sepuluh kali (1000 menjadi 10000), nilainya naik seratus kali (1.000.000 menjadi 100.000.000). Sementara itu O(n log n) hanya naik sekitar 13 kali dan O(log n) naik sekitar 3-4 kali. Inilah “bentuk kurva” yang dimaksud Big-O.

Aturan Menghitung Big-O dari Kode #

Membaca Big-O dari kode menjadi rutinitasan setelah kita terbiasa dengan lima aturan berikut:

1. Buang konstanta: 3n + 2 dihitung O(n), karena faktor pengali tetap tidak mengubah bentuk pertumbuhan.
2. Ambil suku dominan: n² + 10n + 500 dihitung O(n²), karena saat n besar suku n² yang menentukan.
3. Berurutan: dijumlahkan, lalu ambil dominan: dua perulangan linear satu sama lain tetap O(n).
4. Bersarang: dikalikan: perulangan O(n) di dalam perulangan O(n) menjadi O(n²).
5. Membagi dua setiap langkah → logaritmik: while (n > 1) n /= 2; adalah O(log n); hal serupa terjadi pada binary search.

Aturan-aturan ini bekerja dua arah: kita bisa memperkirakan biaya kode yang sedang ditulis, dan bisa menebak isi sebuah fungsi hanya dari kompleksitas yang didokumentasikan. Halaman cppreference misalnya mencantumkan bahwa std::sort berjalan dalam O(n log n) dan akses elemen std::vector melalui operator[] berjalan dalam O(1) — dua fakta yang sekarang sudah kita pahami alasannya.

Best, Average, dan Worst Case #

Satu algoritma bisa punya biaya berbeda untuk input yang berbeda. Linear search pada array berisi n elemen menemukan target di elemen pertama dengan 1 perbandingan (best case O(1)), rata-rata memeriksa sekitar n/2 elemen (average case O(n)), dan memeriksa seluruh n elemen bila target berada di akhir atau tidak ada (worst case O(n)). Ketika seseorang menulis “linear search adalah O(n)”, yang dimaksud biasanya worst case — jaminan atas kerja terburuk yang mungkin.

Kebiasaan bertanya “worst case-nya apa?” akan sangat berguna saat kita memilih struktur data di akhir section ini. Chapter berikutnya mulai membangun fondasi praktisnya: array statis dan dynamic array, tempat kita menghitung sendiri biaya push_back yang tampak O(1) itu.

Rujukan resmi: std::vector dan std::sort .