Dua program bisa menghasilkan output yang sama, tetapi biayanya berbeda ribuan kali lipat. Ketika data yang diolah masih sepuluh elemen, perbedaan tersebut nyaris tak terasa; ketika data mencapai sejuta elemen, algoritma yang salah membuat aplikasi terasa lambat drastis. Kompleksitas adalah cara kita mengukur biaya algoritma sebelum program benar-benar dijalankan pada data besar. Pada Chapter ini kita belajar menghitung operasi dasar secara eksak dengan penghitung (counter), mengenali kelas kompleksitas yang umum, membedakan kasus terbaik, terburuk, dan rata-rata, serta melihat tukar-menukar antara ruang memori dan waktu eksekusi.

Menghitung Operasi Dasar #

Mengukur kompleksitas tidak dimulai dari detik atau milidetik. Durasi bergantung pada kecepatan prosesor, beban mesin, dan compiler JIT — angka yang berubah setiap eksekusi. Pendekatan yang stabil adalah menghitung operasi dasar: berapa kali elemen dibandingkan, atau berapa kali loop paling dalam berjalan. Operasi semacam ini punya sifat yang sangat berguna: jumlahnya identik di mesin mana pun, sehingga angkanya bisa dibandingkan dan diverifikasi.

Program berikut memasang penghitung statis operasi ke empat algoritma kecil, lalu mencetak jumlah operasi eksak pada array 1000 elemen. Perhatikan khususnya pasangan cariBiner dan cariLinier yang sama-sama mencari nilai 1000:

java MenghitungOperasi.java 
public class MenghitungOperasi {

    // Penghitung operasi dasar: deterministik, tidak memakai jam/pengukuran waktu.
    static long operasi = 0;

    public static void main(String[] args) {
        int n = 1000;
        int[] data = new int[n];
        for (int i = 0; i < n; i++) {
            data[i] = i + 1; // 1..1000, sudah terurut
        }

        System.out.println("=== Operasi dasar pada array " + n + " elemen ===");

        operasi = 0;
        int maks = cariMaks(data);
        System.out.println("cariMaks        -> hasil " + maks
                + ", perbandingan elemen: " + operasi);

        operasi = 0;
        long pasangan = hitungPasangan(data);
        System.out.println("hitungPasangan  -> hasil " + pasangan
                + ", iterasi loop dalam: " + operasi);

        operasi = 0;
        int indeksBiner = cariBiner(data, 1000);
        System.out.println("cariBiner(1000) -> indeks " + indeksBiner
                + ", perbandingan: " + operasi);

        operasi = 0;
        int indeksLinier = cariLinier(data, 1000);
        System.out.println("cariLinier(1000)-> indeks " + indeksLinier
                + ", perbandingan: " + operasi);

        System.out.println();
        System.out.println("=== Kasus terbaik, terburuk, rata-rata (n=100) ===");
        demoKasus();
    }

    static int cariMaks(int[] a) {
        int maks = a[0];
        for (int i = 1; i < a.length; i++) {
            operasi++;              // satu perbandingan elemen
            if (a[i] > maks) {
                maks = a[i];
            }
        }
        return maks;
    }

    static long hitungPasangan(int[] a) {
        long jumlah = 0;
        for (int i = 0; i < a.length; i++) {
            for (int j = i + 1; j < a.length; j++) {
                operasi++;          // satu iterasi loop dalam
                jumlah += a[i] + a[j];
            }
        }
        return jumlah;
    }

    static int cariLinier(int[] a, int target) {
        for (int i = 0; i < a.length; i++) {
            operasi++;              // satu perbandingan elemen
            if (a[i] == target) {
                return i;
            }
        }
        return -1;
    }

    static int cariBiner(int[] a, int target) {
        int lo = 0;
        int hi = a.length - 1;
        while (lo <= hi) {
            int mid = (lo + hi) >>> 1;
            operasi++;              // satu perbandingan dengan elemen tengah
            if (a[mid] == target) {
                return mid;
            } else if (a[mid] < target) {
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }
        return -1;
    }

    static void demoKasus() {
        int n = 100;
        int[] data = new int[n];
        for (int i = 0; i < n; i++) {
            data[i] = i + 1;
        }

        operasi = 0;
        cariLinier(data, 1);        // target berada di indeks 0
        long terbaik = operasi;

        operasi = 0;
        cariLinier(data, 100);      // target berada di indeks terakhir
        long terburuk = operasi;

        operasi = 0;
        cariLinier(data, 999);      // target tidak ada di array
        long tidakAda = operasi;

        long total = 0;
        for (int target = 1; target <= n; target++) {
            operasi = 0;
            cariLinier(data, target);
            total += operasi;
        }
        double rata = (double) total / n;

        System.out.printf("Target di indeks 0  : %d perbandingan (kasus terbaik)%n", terbaik);
        System.out.printf("Target di indeks %d: %d perbandingan (kasus terburuk)%n", n - 1, terburuk);
        System.out.printf("Target tidak ada    : %d perbandingan (kasus terburuk)%n", tidakAda);
        System.out.printf("Rata-rata 100 target: %.1f perbandingan%n", rata);
    }
}

Output yang Dihasilkan:

text 
=== Operasi dasar pada array 1000 elemen ===
cariMaks        -> hasil 1000, perbandingan elemen: 999
hitungPasangan  -> hasil 499999500, iterasi loop dalam: 499500
cariBiner(1000) -> indeks 999, perbandingan: 10
cariLinier(1000)-> indeks 999, perbandingan: 1000

=== Kasus terbaik, terburuk, rata-rata (n=100) ===
Target di indeks 0  : 1 perbandingan (kasus terbaik)
Target di indeks 99: 100 perbandingan (kasus terburuk)
Target tidak ada    : 100 perbandingan (kasus terburuk)
Rata-rata 100 target: 50.5 perbandingan

Hasilnya sangat jelas: mencari nilai terbesar pada 1000 elemen hanya butuh 999 perbandingan, sedangkan pencarian biner untuk nilai 1000 hanya butuh 10 perbandingan. Bandingkan dengan pencarian linier yang memeriksa seluruh 1000 elemen. Mari kita telaah bagian-bagian pentingnya:

  1. Baris 4 (static long operasi = 0;): satu field penghitung bersama. Sebelum memanggil tiap algoritma, field ini di-reset ke 0 agar hasil pengukuran tidak tercampur antar-algoritma.
  2. Baris 45-47 (operasi++; di cariMaks): kenaikan dilakukan setiap satu perbandingan elemen dijalankan. Karena loop berjalan dari indeks 1 sampai 999, total kenaikannya 999 — persis rumus n−1.
  3. Baris 55-57 (operasi++; di hitungPasangan): penghitung diletakkan di loop paling dalam. Loop bersarang i lalu j = i+1 menghasilkan 1000·999/2 = 499500 iterasi — pertumbuhan kuadratik yang mulai terasa nyata.
  4. Baris 82 (int mid = (lo + hi) >>> 1;): operator unsigned shift membagi dua rentang pencarian tanpa risiko luber (overflow) pada penjumlahan lo + hi. Setiap iterasi memotong ruang pencarian menjadi setengahnya, sehingga 1000 elemen habis dalam 10 langkah karena 2¹⁰ = 1024 ≥ 1000.

Kelas Kompleksitas yang Umum #

Hasil penghitungan di atas adalah bentuk umum dari kelas kompleksitas. Tabel berikut merangkum kelas yang paling sering muncul, dari yang paling murah hingga paling berat:

KelasNamaContoh nyata
O(1)konstantaakses array[indeks], push stack
O(log n)logaritmikpencarian biner, operasi poll heap
O(n)linierpencarian linier, penelusuran array satu loop
O(n log n)liniritmikmerge sort, quick sort rata-rata
O(n²)kuadratikbubble sort, loop bersarang penuh
O(n³)kubikperkalian matriks naive
O(2ⁿ)eksponensialfibonacci rekursif naive, subset lengkap
O(n!)faktorialbrute force semua permutasi

Satu catatan penting: ruang memori punya kelas yang sama. Sebuah algoritma bisa O(n) waktu tetapi O(1) ruang, atau sebaliknya menyimpan tabel berukuran O(n) supaya hitungan tidak diulang.

Kasus Terbaik, Terburuk, dan Rata-rata #

Jumlah operasi algoritma yang sama bisa berbeda bergantung pada posisi data. Bagian demoKasus pada program di atas membuktikannya pada array 100 elemen: target di indeks 0 selesai dalam 1 perbandingan (kasus terbaik), target di indeks terakhir dan target yang tidak ada masing-masing memakan 100 perbandingan (kasus terburuk), sedangkan rata-rata dari 100 target yang pasti ditemukan adalah 50,5 perbandingan. Ketika kita menyebut “linear search adalah O(n)”, yang dimaksud adalah kasus terburuk — batas atas yang tidak akan dilampaui berapa pun susunan datanya. Konvensi ini penting karena kasus terbaik jarang bisa diandalkan, sedangkan kasus terburuk memberi jaminan.

Ruang dan Waktu Saling Ditukar #

Sering kali kita bisa membayar ruang memori tambahan untuk membeli waktu. Program kedua menghitung fibonacci ke-30 dengan dua strategi: versi pertama hanya menyimpan dua nilai terakhir (2 slot), versi kedua menyimpan tabel dp berisi seluruh 31 nilai antara:

java RuangVsWaktu.java 
public class RuangVsWaktu {

    public static void main(String[] args) {
        int n = 30;
        long hasilA = fibDuaVariabel(n);
        long hasilB = fibTabel(n);

        System.out.println("Fibonacci ke-" + n + " = " + hasilA);
        System.out.println("Versi dua variabel : 2 slot long, waktu O(n)");
        System.out.println("Versi tabel dp     : " + (n + 1) + " slot long, waktu O(n)");
        System.out.println("Hasil kedua versi sama: " + (hasilA == hasilB));
    }

    // Versi hemat ruang: hanya menyimpan dua nilai terakhir.
    static long fibDuaVariabel(int n) {
        long a = 0; // fib(0)
        long b = 1; // fib(1)
        for (int i = 1; i <= n; i++) {
            long berikutnya = a + b;
            a = b;
            b = berikutnya;
        }
        return a;
    }

    // Versi boros ruang: menyimpan seluruh tabel hasil antara.
    static long fibTabel(int n) {
        long[] dp = new long[n + 1];
        dp[0] = 0;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
}

Output yang Dihasilkan:

text 
Fibonacci ke-30 = 832040
Versi dua variabel : 2 slot long, waktu O(n)
Versi tabel dp     : 31 slot long, waktu O(n)
Hasil kedua versi sama: true

Kedua versi menghasilkan angka yang sama, yaitu 832040, dengan waktu yang sama-sama linier. Versi tabel menjadi berguna saat setiap nilai antara akan dipakai ulang berulang kali — misalnya pada dynamic programming yang kita bahas nanti; ketika hasil antara tidak pernah dibaca lagi, dua variabel sudah cukup. Keputusan “ruang dibeli demi waktu” seperti ini muncul terus dalam rekayasa algoritma.

Dengan cara menghitung operasi ini, kita sudah punya alat ukur yang objektif. Langkah berikutnya adalah membaca dan menuliskan angka-angka tersebut dalam bahasa standar industri: notasi Big-O, beserta aturan membuang konstanta dan suku rendahnya.

Referensi #

Berkas Sumber

Berkas pendukung halaman ini dapat diunduh dan dijalankan langsung sesuai penjelasan di atas.

MenghitungOperasi.java

Unduh berkas
java 
public class MenghitungOperasi {

    // Penghitung operasi dasar: deterministik, tidak memakai jam/pengukuran waktu.
    static long operasi = 0;

    public static void main(String[] args) {
        int n = 1000;
        int[] data = new int[n];
        for (int i = 0; i < n; i++) {
            data[i] = i + 1; // 1..1000, sudah terurut
        }

        System.out.println("=== Operasi dasar pada array " + n + " elemen ===");

        operasi = 0;
        int maks = cariMaks(data);
        System.out.println("cariMaks        -> hasil " + maks
                + ", perbandingan elemen: " + operasi);

        operasi = 0;
        long pasangan = hitungPasangan(data);
        System.out.println("hitungPasangan  -> hasil " + pasangan
                + ", iterasi loop dalam: " + operasi);

        operasi = 0;
        int indeksBiner = cariBiner(data, 1000);
        System.out.println("cariBiner(1000) -> indeks " + indeksBiner
                + ", perbandingan: " + operasi);

        operasi = 0;
        int indeksLinier = cariLinier(data, 1000);
        System.out.println("cariLinier(1000)-> indeks " + indeksLinier
                + ", perbandingan: " + operasi);

        System.out.println();
        System.out.println("=== Kasus terbaik, terburuk, rata-rata (n=100) ===");
        demoKasus();
    }

    static int cariMaks(int[] a) {
        int maks = a[0];
        for (int i = 1; i < a.length; i++) {
            operasi++;              // satu perbandingan elemen
            if (a[i] > maks) {
                maks = a[i];
            }
        }
        return maks;
    }

    static long hitungPasangan(int[] a) {
        long jumlah = 0;
        for (int i = 0; i < a.length; i++) {
            for (int j = i + 1; j < a.length; j++) {
                operasi++;          // satu iterasi loop dalam
                jumlah += a[i] + a[j];
            }
        }
        return jumlah;
    }

    static int cariLinier(int[] a, int target) {
        for (int i = 0; i < a.length; i++) {
            operasi++;              // satu perbandingan elemen
            if (a[i] == target) {
                return i;
            }
        }
        return -1;
    }

    static int cariBiner(int[] a, int target) {
        int lo = 0;
        int hi = a.length - 1;
        while (lo <= hi) {
            int mid = (lo + hi) >>> 1;
            operasi++;              // satu perbandingan dengan elemen tengah
            if (a[mid] == target) {
                return mid;
            } else if (a[mid] < target) {
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }
        return -1;
    }

    static void demoKasus() {
        int n = 100;
        int[] data = new int[n];
        for (int i = 0; i < n; i++) {
            data[i] = i + 1;
        }

        operasi = 0;
        cariLinier(data, 1);        // target berada di indeks 0
        long terbaik = operasi;

        operasi = 0;
        cariLinier(data, 100);      // target berada di indeks terakhir
        long terburuk = operasi;

        operasi = 0;
        cariLinier(data, 999);      // target tidak ada di array
        long tidakAda = operasi;

        long total = 0;
        for (int target = 1; target <= n; target++) {
            operasi = 0;
            cariLinier(data, target);
            total += operasi;
        }
        double rata = (double) total / n;

        System.out.printf("Target di indeks 0  : %d perbandingan (kasus terbaik)%n", terbaik);
        System.out.printf("Target di indeks %d: %d perbandingan (kasus terburuk)%n", n - 1, terburuk);
        System.out.printf("Target tidak ada    : %d perbandingan (kasus terburuk)%n", tidakAda);
        System.out.printf("Rata-rata 100 target: %.1f perbandingan%n", rata);
    }
}

RuangVsWaktu.java

Unduh berkas
java 
public class RuangVsWaktu {

    public static void main(String[] args) {
        int n = 30;
        long hasilA = fibDuaVariabel(n);
        long hasilB = fibTabel(n);

        System.out.println("Fibonacci ke-" + n + " = " + hasilA);
        System.out.println("Versi dua variabel : 2 slot long, waktu O(n)");
        System.out.println("Versi tabel dp     : " + (n + 1) + " slot long, waktu O(n)");
        System.out.println("Hasil kedua versi sama: " + (hasilA == hasilB));
    }

    // Versi hemat ruang: hanya menyimpan dua nilai terakhir.
    static long fibDuaVariabel(int n) {
        long a = 0; // fib(0)
        long b = 1; // fib(1)
        for (int i = 1; i <= n; i++) {
            long berikutnya = a + b;
            a = b;
            b = berikutnya;
        }
        return a;
    }

    // Versi boros ruang: menyimpan seluruh tabel hasil antara.
    static long fibTabel(int n) {
        long[] dp = new long[n + 1];
        dp[0] = 0;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
}