Pada chapter sebelumnya kita menghitung operasi dasar untuk algoritma tertentu dan melihat bahwa pertumbuhan bisa linear (2n + 1) atau kuadratik (n^2). Namun, menulis “2n + 1 operasi” tidak praktis karena jumlah konstanta bergantung pada compiler, hardware, dan optimisasi yang dilakukan. Notasi Big O memecahkan masalah ini dengan menyatakan pertumbuhan secara asimptotik—kita mengabaikan konstanta dan hanya memperhatikan suku yang dominan. Pada chapter ini kita akan mempelajari kelas-kelas umum Big O dari O(1) sampai O(n^2), lalu membandingkan waktu eksekusi empiris untuk masing-masing kelas.

Definisi Notasi Big O #

Notasi Big O mendeskripsikan upper bound asimptotik dari sebuah fungsi. Untuk sebuah algoritma dengan waktu eksekusi f(n), kita menulis f(n) = O(g(n)) bila terdapat konstanta c > 0 dan n0 sehingga untuk semua n > n0, berlaku f(n) <= c * g(n). Praktisnya, kita mengambil suku dominan dan membuang konstanta:

  • 2n + 1 → O(n) (linear)
  • n^2 + 5n + 7 → O(n^2) (kuadratik)
  • 3 log n + 10 → O(log n) (logaritmik)

Selain Big O, ada dua notasi pendamping: Big Omega (Ω) yang merupakan lower bound, dan Big Theta (Θ) yang berarti tight bound (kedua-duanya). Dalam praktik sehari-hari, kita hampir selalu menggunakan Big O karena pertumbuhan terburuk adalah yang paling penting dipertimbangkan.

Kelas Umum Kompleksitas #

Kita akan melihat empat kelas paling umum dengan contoh kode ringkas. Setiap kelas menunjukkan pola pertumbuhan berbeda ketika ukuran input berlipat ganda.

c 
#include <stdio.h>

/* O(1): ambil elemen pertama */
int ambil_pertama(const int *a) {
    return a[0];
}

/* O(log n): bagi n terus-menerus sampai 1 */
int hitung_pembagian(int n) {
    int langkah = 0;
    while (n > 1) {
        n /= 2;
        langkah++;
    }
    return langkah;
}

/* O(n): jumlahkan seluruh elemen */
int jumlah_semua(const int *a, int n) {
    int total = 0;
    for (int i = 0; i < n; i++) total += a[i];
    return total;
}

/* O(n^2): hitung semua pasangan */
int hitung_pasangan(int n) {
    int total = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            total++;
    return total;
}

int main(void) {
    int a[] = {5, 10, 15, 20, 25, 30, 35, 40};

    printf("O(1)    ambil_pertama(a)        = %d\n", ambil_pertama(a));

    printf("n       langkah O(log n)\n");
    for (int n = 1; n <= 64; n *= 2) {
        printf("%-8d%d\n", n, hitung_pembagian(n));
    }

    printf("\nO(n)    jumlah_semua(a, 8)      = %d\n", jumlah_semua(a, 8));

    printf("\nn       pasangan O(n^2)\n");
    for (int n = 1; n <= 8; n++) {
        printf("%-8d%d\n", n, hitung_pasangan(n));
    }
    return 0;
}

Output yang Dihasilkan:

text 
O(1)    ambil_pertama(a)        = 5
n       langkah O(log n)
1       0
2       1
4       2
8       3
16      4
32      5
64      6

O(n)    jumlah_semua(a, 8)      = 180

n       pasangan O(n^2)
1       1
2       4
3       9
4       16
5       25
6       36
7       49
8       64

Tiga pola di atas menunjukkan karakteristik tipikal:

  • O(1): konstan—waktu tidak bergantung pada n. Mengakses elemen array via indeks adalah O(1) karena hanya satu penjumlahan pointer.
  • O(log n): setiap n dilipatgandakan, langkah bertambah 1. Bila n naik dari 32 ke 64 (dua kali lipat), langkah hanya naik dari 5 ke 6.
  • O(n): linear—jumlah operasi sama dengan n. n=8 menghasilkan 8 iterasi.
  • O(n^2): kuadratik—n dilipatgandakan menghasilkan empat kali lipat operasi. n=4 menghasilkan 16; n=8 menghasilkan 64.

Mari kita telaah baris-baris kode di atas:

  1. Baris 5-7 (ambil_pertama): fungsi hanya mengembalikan a[0]. Tidak ada loop, tidak ada rekursi—kompleksitasnya konstan O(1) terlepas dari n.
  2. Baris 10-17 (hitung_pembagian): loop membagi n dengan 2 tiap iterasi. Setelah k iterasi, n berkurang menjadi n / 2^k; loop berhenti saat n / 2^k = 1, yaitu k = log2(n). Maka operasi O(log n).
  3. Baris 20-25 (jumlah_semua): loop for sederhana dari 0 sampai n-1. Setiap iterasi melakukan satu operasi penjumlahan. Maka O(n).
  4. Baris 28-34 (hitung_pasangan): dua loop bersarang. Loop luar n kali, loop dalam n kali—total n * n = n^2 iterasi. Maka O(n^2).
  5. Baris 36-55 (main): menjalankan tiap fungsi untuk beberapa nilai n agar pertumbuhan terlihat di output.

Perbandingan Waktu Empiris #

Sekarang kita akan membandingkan empat kelas—O(n), O(n log n), dan O(n^2)—dengan mengukur waktu eksekusi pada ukuran input yang berbeda. Untuk O(1) dan O(log n) waktunya terlalu singkat untuk diukur dengan clock(), jadi kita skip dan fokus pada tiga kelas lain.

c 
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int linear_search(const int *a, int n, int target) {
    for (int i = 0; i < n; i++) {
        if (a[i] == target) return i;
    }
    return -1;
}

void merge(int *a, int *tmp, int kiri, int mid, int kanan) {
    int i = kiri, j = mid, k = kiri;
    while (i < mid && j <= kanan) {
        if (a[i] <= a[j]) tmp[k++] = a[i++];
        else tmp[k++] = a[j++];
    }
    while (i < mid) tmp[k++] = a[i++];
    while (j <= kanan) tmp[k++] = a[j++];
    for (int t = kiri; t <= kanan; t++) a[t] = tmp[t];
}

void merge_sort(int *a, int *tmp, int kiri, int kanan) {
    if (kiri >= kanan) return;
    int mid = kiri + (kanan - kiri) / 2;
    merge_sort(a, tmp, kiri, mid);
    merge_sort(a, tmp, mid + 1, kanan);
    merge(a, tmp, kiri, mid + 1, kanan);
}

void bubble_sort(int *a, int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (a[j] > a[j + 1]) {
                int t = a[j]; a[j] = a[j + 1]; a[j + 1] = t;
            }
        }
    }
}

int main(void) {
    int ukuran[] = {1000, 5000, 10000, 50000};
    int k = sizeof(ukuran) / sizeof(ukuran[0]);

    printf("%-8s %-12s %-14s %-12s\n", "n", "O(n)", "O(n log n)", "O(n^2)");
    for (int i = 0; i < k; i++) {
        int n = ukuran[i];
        int *a = malloc(sizeof(int) * (size_t)n);
        int *tmp = malloc(sizeof(int) * (size_t)n);
        for (int j = 0; j < n; j++) a[j] = n - j;

        clock_t s = clock();
        linear_search(a, n, -1);
        double tn = (double)(clock() - s) / CLOCKS_PER_SEC;

        s = clock();
        merge_sort(a, tmp, 0, n - 1);
        double tnl = (double)(clock() - s) / CLOCKS_PER_SEC;

        for (int j = 0; j < n; j++) a[j] = n - j;
        double tq;
        if (n <= 10000) {
            s = clock();
            bubble_sort(a, n);
            tq = (double)(clock() - s) / CLOCKS_PER_SEC;
        } else {
            tq = -1.0;
        }

        printf("%-8d %-12.6f %-14.6f ", n, tn, tnl);
        if (tq < 0) printf("%-12s\n", "(skip)"); else printf("%-12.6f\n", tq);

        free(a);
        free(tmp);
    }
    return 0;
}

Output yang Dihasilkan:

text 
n        O(n)         O(n log n)     O(n^2)      
1000     0.000003     0.000117       0.004413    
5000     0.000010     0.000632       0.109710    
10000    0.000021     0.001313       0.434611    
50000    0.000101     0.007574       (skip)

Pada n = 10.000, bubble sort O(n^2) memerlukan 0,43 detik—sekitar 200 kali lebih lambat dibanding merge sort O(n log n) (0,0013 detik). Pada n = 50.000 kita sengaja melewatkan bubble sort karena akan memerlukan waktu lebih dari 10 detik. Inilah mengapa pada data besar, perbedaan kelas Big O bukan sekadar teori—perbedaan waktu eksekusi bisa mencapai ratusan atau ribuan kali.

Hierarki Kelas Big O #

Tabel berikut merangkum kelas Big O dari yang paling cepat hingga paling lambat, beserta contoh algoritma yang umum untuk masing-masing kelas:

KelasNamaContoh algoritma
O(1)KonstanHash table lookup, akses array via indeks
O(log n)LogaritmikBinary search, operasi tree balanced
O(n)LinearLinear search, traversal linked list
O(n log n)LinearithmicMerge sort, quicksort average, heap sort
O(n^2)KuadratikBubble sort, selection sort, insertion sort
O(n^3)KubikPerkalian matriks naive
O(2^n)EksponensialSubset sum, TSP brute force
O(n!)FaktorialPermutasi semua elemen

Dengan pemahaman ini, kita siap masuk ke chapter-chapter algoritma spesifik. Setiap kali kita memperkenalkan algoritma baru, kita akan menyebutkan kelas Big O-nya dan menjelaskan dari mana kelas tersebut muncul.