Kelas kompleksitas umum

Enam kelas kompleksitas mencakup hampir semua algoritma yang ditemui sehari-hari, dari sekadar mengambil satu elemen hingga mencoba semua kemungkinan. Topik ini memetakan keenamnya ke situasi nyata, menaksir jumlah langkahnya pada beberapa ukuran masukan, lalu membuktikan selisih dua kelasnya dengan penghitung operasi dan pengukuran detik. Setelah membacanya, notasi seperti $O(n \log n)$ terasa seperti nama tempat yang pernah dikunjungi, bukan istilah asing.

Enam kelas dan situasinya#

Sebuah kelas kompleksitas mengelompokkan algoritma yang jumlah operasinya tumbuh dengan bentuk kurva yang sama. Dua algoritma pada kelas yang sama boleh berbeda detail konstantanya, tetapi keduanya melengkung dengan cara yang sama ketika masukan membesar. Tabel berikut memasangkan setiap kelas dengan situasi yang memunculkannya.

Dua kelas di tengah layak diberi perhatian ekstra. Kelas $O(\log n)$ hampir selalu muncul dari strategi membagi ruang kerja menjadi separuh di setiap langkah, sehingga ruang berisi 1.000.000 kandidat habis dalam sekitar 20 langkah. Kelas $O(n \log n)$ adalah tempat berdirinya pengurutan efisien seperti merge sort, yaitu pengurutan yang membagi daftar kecil-kecil lalu menggabungkan hasilnya kembali. Ada $\log n$ tingkat pembagian, dan setiap tingkat masih perlu menyapu $n$ elemen.

Taksiran langkah pada tiga ukuran#

Tabel berikut menaksir jumlah langkah pada $n$ sebesar 10, 1.000, dan 1.000.000. Logaritma memakai basis dua, dan nilai pembulatannya ditandai $\approx$. Angka pasti bukan targetnya, melainkan cara setiap baris bereaksi ketika kolom $n$ bergeser ke kanan.

Baris terakhir menjelaskan mengapa brute force, yaitu strategi mencoba semua kemungkinan tanpa memangkas apa pun, selalu gagal pada masukan besar. Menambah satu elemen menggandakan seluruh pekerjaannya, sehingga masukan berisi 30 elemen saja sudah menuntut sekitar satu miliar langkah. Sebaliknya, dua baris teratas hampir tidak merasakan pergantian kolom. Yang masih layak dihitung pada kolom paling kanan hanyalah empat baris teratas, dan empat baris itulah wilayah tempat algoritma sehari-hari dirancang. Perbedaan ini yang membuat pemilihan algoritma lebih menentukan daripada kecepatan mesin.

Pencarian linear versus pencarian biner#

Selisih antar kelas paling mudah dirasakan pada dua algoritma yang menyelesaikan tugas yang sama. Pencarian linear menyusuri daftar satu per satu sehingga berada di kelas $O(n)$, sedangkan pencarian biner membelah daftar terurut menjadi separuh pada setiap langkah sehingga berada di kelas $O(\log n)$. Berkas berikut menghitung langkah keduanya pada daftar sejuta elemen dengan target di ujung akhir, yaitu posisi terburuk bagi pencarian linear.

# Jumlah langkah pencarian linear dan pencarian biner.
# Target dipilih di ujung daftar agar pencarian linear masuk ke
# kasus terburuk, yaitu memeriksa seluruh isi daftar.

def cari_linear(data, target):
    langkah = 0
    for nilai in data:
        langkah += 1
        if nilai == target:
            return langkah
    return langkah

def cari_biner(data, target):
    kiri, kanan = 0, len(data) - 1
    langkah = 0
    while kiri <= kanan:
        langkah += 1
        tengah = (kiri + kanan) // 2
        if data[tengah] == target:
            return langkah
        if data[tengah] < target:
            kiri = tengah + 1
        else:
            kanan = tengah - 1
    return langkah

data = list(range(1, 1_000_001))
target = 1_000_000
print(f"ukuran data      : {len(data)} elemen")
print(f"pencarian linear : {cari_linear(data, target)} langkah")
print(f"pencarian biner  : {cari_biner(data, target)} langkah")

ukuran data      : 1000000 elemen
pencarian linear : 1000000 langkah
pencarian biner  : 20 langkah

Selisihnya sejuta langkah melawan dua puluh. Angka dua puluh bukan kebetulan, karena $\log_2 1.000.000 \approx 19{,}9$ dan setiap langkah pencarian biner memang membuang separuh kandidat yang tersisa. Target di ujung akhir sengaja dipilih agar pencarian linear menempuh kasus terburuknya, sehingga perbandingan ini mengadu dua kontrak kasus terburuk, bukan dua kasus keberuntungan.

Perbandingan ini juga memperlihatkan syarat yang mudah terlupakan. Pencarian biner hanya berlaku pada daftar yang sudah terurut, sedangkan mengurutkan sendiri berbiaya $O(n \log n)$. Karena itu pencarian biner cocok untuk daftar yang diurutkan sekali lalu dicari berkali-kali, sedangkan pencarian linear tetap menjadi pilihan yang masuk akal untuk daftar yang isinya terus berubah.

Demo yang sama dalam Java#

Bahasa pemrograman tidak mengubah kelas kompleksitas, karena yang dihitung adalah bentuk perulangannya, bukan sintaksnya. Berkas Java berikut meniru penghitungan yang sama dengan struktur yang mirip, dua fungsi berpenghitung langkah dan satu pencetakan hasil. Berkas tunggal tanpa pustaka tambahan seperti ini dijalankan langsung dengan java PencarianLangkah.java.

// Pencarian linear vs pencarian biner dihitung dengan penghitung langkah.
public class PencarianLangkah {
    static int langkahLinear(int[] data, int target) {
        int langkah = 0;
        for (int i = 0; i < data.length; i++) {
            langkah++;
            if (data[i] == target) {
                return langkah;
            }
        }
        return langkah;
    }

    static int langkahBiner(int[] data, int target) {
        int kiri = 0, kanan = data.length - 1, langkah = 0;
        while (kiri <= kanan) {
            langkah++;
            int tengah = (kiri + kanan) / 2;
            if (data[tengah] == target) {
                return langkah;
            }
            if (data[tengah] < target) {
                kiri = tengah + 1;
            } else {
                kanan = tengah - 1;
            }
        }
        return langkah;
    }

    public static void main(String[] args) {
        int n = 1000000;
        int[] data = new int[n];
        for (int i = 0; i < n; i++) {
            data[i] = i + 1;
        }
        int target = n;
        System.out.println("ukuran data      : " + n + " elemen");
        System.out.println("pencarian linear : " + langkahLinear(data, target) + " langkah");
        System.out.println("pencarian biner  : " + langkahBiner(data, target) + " langkah");
    }
}

ukuran data      : 1000000 elemen
pencarian linear : 1000000 langkah
pencarian biner  : 20 langkah

# menjalankan berkas Java tunggal tanpa tahap kompilasi terpisah
java PencarianLangkah.java

ukuran data      : 1000000 elemen
pencarian linear : 1000000 langkah
pencarian biner  : 20 langkah

Keluaran ketiganya identik dengan versi Python, dan memang harus identik karena jumlah langkah adalah sifat algoritmanya, bukan sifat bahasanya. Yang berbeda hanya kecepatan pengerjaan satu langkah, dan kecepatan itu berperan sebagai konstanta yang tidak masuk ke dalam notasi. Inilah alasan penghitung operasi dipilih sebagai alat ukur utama di jalur ini, karena hasilnya dapat dipindahkan antar bahasa tanpa perdebatan.

Struktur kedua berkasnya juga sengaja dibuat sejajar. Fungsi langkahLinear dan langkahBiner di Java berhadapan dengan cari_linear dan cari_biner di Python, dan perulangannya dibaca dengan cara yang sama. Yang berbeda hanya tipe data eksplisit dan penulisan bloknya. Penghitung langkah berada di posisi yang persis sama pada keduanya, sehingga tidak ada satu pun angka yang perlu diubah agar kedua versi menghitung hal yang sama.

Mengukur detik yang sesungguhnya#

Penghitung operasi bersifat deterministik, sedangkan pengukuran detik tidak. Potongan berikut mengukur waktu pencarian linear pada $n$ yang bertambah, dan keluarannya sengaja tidak ditempel karena berubah di setiap mesin dan di setiap eksekusi.

# tidak-dijalankan
# Keluaran berupa detik sehingga berubah di setiap mesin
# dan di setiap eksekusi, maka tidak ditempel sebagai Keluaran.
import time

def cari_linear(data, target):
    for i, nilai in enumerate(data):
        if nilai == target:
            return i
    return -1

target = -1  # tidak pernah ada di daftar, sehingga seluruh isi tersusuri
for n in (10_000, 100_000, 1_000_000):
    data = list(range(n))
    mulai = time.perf_counter()
    cari_linear(data, target)
    print(f"n = {n:9} -> {time.perf_counter() - mulai:.6f} detik")

Sebagai gambaran, satu eksekusi pada mesin yang dipakai untuk menulis modul ini menghasilkan angka berikut, dan eksekusi di mesin lain maupun eksekusi berikutnya akan menghasilkan angka yang berbeda.

Bentuknya yang penting. Setiap $n$ berlipat sepuluh membuat detiknya berlipat sekitar sepuluh, tanda kurva linear, bukan tanda kecepatan mutlak. Untuk pengukuran yang lebih andal, modul timeit pada dokumentasi Python menyediakan cara baku yang mengulang pengukuran berkali-kali lalu merata-ratakannya. Aturan praktisnya, gunakan detik untuk memeriksa bentuk kurva dan gunakan penghitung operasi untuk mengomunikasikan kelasnya.

Ringkasan#

• Enam kelas $O(1)$, $O(\log n)$, $O(n)$, $O(n \log n)$, $O(n^2)$, dan $O(2^n)$ masing-masing dipasangkan dengan situasi yang memunculkannya.
• Tabel taksiran langkah pada $n = 10$, 1.000, dan 1.000.000 memperlihatkan seberapa berbeda reaksi setiap kelas terhadap ukuran masukan.
• Pencarian linear menempuh sejuta langkah pada masukan sejuta elemen, sedangkan pencarian biner cukup dua puluh, dan hasilnya sama di Python maupun Java.
• Detik dipakai untuk memeriksa bentuk kurva, sedangkan penghitung operasi dipakai untuk menyatakan kelas kompleksitas.

Referensi#

• timeit — Dokumentasi Python — Modul baku untuk mengukur waktu eksekusi potongan kode Python secara andal.
• Analysis of algorithms — Wikipedia — Klasifikasi laju pertumbuhan algoritma dan metode pengukurannya.