Intuisi Big-O

Notasi Big-O (Big-O notation) adalah cara menuliskan laju pertumbuhan waktu eksekusi sebuah algoritma terhadap ukuran masukannya. Notasi ini menjawab pertanyaan yang berbeda dari pertanyaan pengukuran biasa, yaitu bagaimana kinerja berubah ketika masukan bertambah, bukan seberapa cepat program berjalan pada satu masukan tertentu. Topik ini membangun intuisi tersebut lewat kurva pertumbuhan dan penghitung operasi, sehingga sebuah notasi seperti $O(n^2)$ dapat dibaca sebagai bentuk kurva, bukan sebagai angka yang dihafal.

Laju pertumbuhan, bukan jumlah detik#

Ukuran pertama dalam analisis algoritma adalah time complexity, yaitu waktu eksekusi yang dinyatakan sebagai fungsi dari ukuran masukan. Fungsinya ditulis $T(n)$, dengan $n$ menyatakan ukuran masukan, misalnya jumlah elemen pada daftar yang akan diproses. Nilai $T(n)$ yang dipakai bukan berupa detik, melainkan jumlah operasi dasar yang dikerjakan, seperti satu perbandingan atau satu penambahan nilai. Detik bergantung pada mesin, bahasa pemrograman, dan beban sistem saat pengukuran, sedangkan jumlah operasi tidak.

Mesin yang berbeda mengeksekusi jumlah operasi yang sama dalam waktu yang berbeda, tetapi pada mesin yang sama jumlah operasi dan waktu tetap sebanding. Program yang mengerjakan dua kali lipat operasi cenderung berjalan dua kali lipat lama. Perbandingan yang adil tetap dilakukan pada masukan yang sama, karena dua algoritma yang diukur pada masukan berbeda tidak memberi informasi apa pun. Karena itu, membandingkan $T(n)$ antar algoritma sudah cukup untuk memprediksi urutan kecepatannya tanpa perlu tahu kecepatan prosesor yang akan menjalankannya. Seluruh pembahasan kompleksitas waktu bergerak di wilayah jumlah operasi, dan detik hanya muncul sebagai pelengkap pengukuran.

Kurva pertumbuhan tiga algoritma#

Bentuk $T(n)$ paling mudah dipahami sebagai kurva pada bidang yang sumbu mendatarnya berisi $n$ dan sumbu tegaknya berisi jumlah operasi. Algoritma konstan mengerjakan jumlah operasi yang sama untuk $n$ kecil maupun besar, sehingga kurvanya mendatar. Algoritma linear naik lurus karena setiap tambahan satu elemen masukan menambah satu operasi. Algoritma kuadrat melengkung naik semakin curam karena setiap tambahan satu elemen menambah kira-kira $2n$ operasi baru.

Diagram berikut menumpukkan tiga kurva tersebut dalam satu bidang, termasuk kurva logaritmik yang akan ditemui lagi pada pencarian biner. Perhatikan bahwa perbedaan ketiganya terasa kecil di ujung kiri dan melebar drastis ke arah kanan. Di sanalah letak pentingnya, karena perbedaan kelas baru benar-benar memutuskan ketika masukan membesar.

Menghitung operasi, bukan menduga-duga#

Cara paling meyakinkan untuk membaca kurva adalah menghitung operasinya langsung. Caranya adalah menyisipkan penghitung operasi, yaitu variabel yang ditambah satu setiap kali pekerjaan inti algoritma dikerjakan, lalu mencetak isinya untuk beberapa ukuran masukan. Berkas berikut menghitung operasi tiga algoritma pada $n = 10$, $n = 100$, dan $n = 1000$. Tiga fungsinya sengaja dibuat sederhana, karena yang dibandingkan adalah bentuk perulangannya, bukan kegunaannya.

# Penghitung operasi untuk tiga kurva pertumbuhan.
# Tabel menunjukkan jumlah operasi pada n = 10, 100, dan 1000.

def algoritma_konstan(n):
    langkah = 1                 # satu akses, tidak tergantung ukuran n
    return langkah

def algoritma_linear(n):
    langkah = 0
    for _ in range(n):          # setiap elemen disinggung sekali
        langkah += 1
    return langkah

def algoritma_kuadrat(n):
    langkah = 0
    for _ in range(n):          # setiap pasangan elemen dibandingkan
        for _ in range(n):
            langkah += 1
    return langkah

print(f"{'n':>6} {'konstan':>9} {'linear':>8} {'kuadrat':>9}")
for n in (10, 100, 1000):
    k = algoritma_konstan(n)
    l = algoritma_linear(n)
    q = algoritma_kuadrat(n)
    print(f"{n:>6} {k:>9} {l:>8} {q:>9}")

     n   konstan   linear   kuadrat
    10         1       10       100
   100         1      100     10000
  1000         1     1000   1000000

Berkasnya berdiri sendiri, sehingga dapat dijalankan langsung dari terminal di dalam folder topik ini. Perintahnya dijalankan di folder tempat berkasnya berada, dan keluarannya persis sama dengan tabel di atas.

# menjalankan demo penghitung operasi dari terminal
python3 penghitung-operasi.py

     n   konstan   linear   kuadrat
    10         1       10       100
   100         1      100     10000
  1000         1     1000   1000000

Baca tabelnya kolom demi kolom. Kolom konstan membeku pada angka 1 karena tidak menyentuh ukuran masukan. Kolom linear berlipat sepuluh setiap $n$ berlipat sepuluh, sedangkan kolom kuadrat berlipat seratus. Bila tabel diperpanjang ke $n = 10000$, kolom linear cukup sepuluh ribu operasi, sedangkan kolom kuadrat menuntut seratus juta. Pola berlipat inilah sidik jari setiap kelas, dan sidik jari ini yang dipakai untuk membaca notasi $O(1)$, $O(n)$, dan $O(n^2)$.

Mengapa konstanta dan suku rendah diabaikan#

Fungsi waktu yang sesungguhnya jarang serapi $n$ atau $n^2$. Algoritma yang menyusuri daftar sekali mungkin mengerjakan $3n + 7$ operasi, dan algoritma berpasangan mungkin mengerjakan $\frac{n^2}{2} + 100n$ operasi. Notasi Big-O membuang konstanta dan suku rendah, sehingga keduanya ditulis $O(n)$ dan $O(n^2)$. Pemangkasan ini bukan kesepakatan kosong, melainkan konsekuensi dari pertanyaan yang dijawabnya, yaitu bentuk kurva ketika $n$ membesar.

Angka konkret memperlihatkan kapan pemangkasan itu aman. Ambil $T(n) = 0{,}001\,n^2 + 100n$. Pada $n$ sebesar 10.000, suku linear masih menyumbang 1.000.000 operasi, jauh di atas 100.000 operasi suku kuadrat. Kedua suku berimbang tepat pada $n$ sebesar 100.000, lalu keadaan terbalik di atasnya, karena rasio $\frac{100n}{n^2} = \frac{100}{n}$ terus menyusut menuju nol. Untuk $n$ yang besar, hanya suku dengan laju tumbuh tertinggi yang terasa. Konstanta hanya menentukan posisi kurva pada ukuran kecil, bukan urutan antar kelas pada ukuran besar.

Kasus terburuk sebagai kontrak#

Jumlah operasi sebuah algoritma tidak hanya bergantung pada $n$, tetapi juga pada isi masukannya. Pencarian linear pada daftar berisi $n$ nilai butuh satu langkah bila targetnya ada di awal, dan $n$ langkah bila targetnya ada di akhir atau tidak ada sama sekali. Kondisi terburuk itu disebut worst case, yaitu masukan yang memaksa jumlah operasi paling banyak untuk ukuran $n$ tertentu.

Big-O yang dikutip pada dokumentasi dan wawancara biasanya merujuk kasus terburuk, sehingga notasinya bekerja sebagai kontrak. Tidak ada masukan berukuran $n$ yang membuat algoritma lebih lambat dari yang dijanjikan. Janji semacam ini disebut upper bound, yaitu batas atas jumlah operasi. Cara membaca yang aman adalah memperlakukan $O(n)$ pada sebuah fungsi sebagai dinding berbentuk kurva linear, yang tidak boleh dilampaui jumlah operasi untuk masukan apa pun.

Ringkasan#

• Big-O menuliskan laju pertumbuhan jumlah operasi terhadap ukuran masukan, bukan jumlah detik.
• $O(1)$, $O(n)$, dan $O(n^2)$ dikenali dari pola berlipatnya ketika $n$ berlipat sepuluh, yaitu tetap, sepuluh kali, dan seratus kali.
• Konstanta dan suku rendah diabaikan karena suku dengan laju tumbuh tertinggi mendominasi pada masukan besar.
• Notasi yang dikutip biasanya berlaku untuk kasus terburuk dan berfungsi sebagai batas atas.

Referensi#

• Big O notation — Wikipedia — Definisi formal notasi Big-O beserta contoh dan sejarahnya.
• Analysis of algorithms — Wikipedia — Ringkasan metode analisis laju pertumbuhan algoritma, termasuk kasus terburuk.