Bagaimana Biaya Tumbuh

Big O mengukur bagaimana biaya tumbuh saat input tumbuh. Bukan faktor konstan - laju pertumbuhan. Dua algoritma yang keduanya berjalan dalam 'beberapa milidetik' pada N=100 mungkin berbeda oleh faktor 10.000 pada N=10.000, jika satu berjalan dalam O(N) waktu & yang lain dalam O(N²).

Kelas Kompleksitas Umum

O(1) — Konstan. Biaya yang sama terlepas dari N. Contoh: pencarian hash tabel oleh kunci, akses array oleh indeks, push/pop stack. Menggandakan N tidak mengubah apa-apa.

O(log N) — Logaritmik. Setiap langkah mengurangi setengah pekerjaan yang tersisa. Contoh: pencarian biner dalam array yang terurut, kueri spatial BVH di mesin game, operasi pohon biner seimbang. Pada N=1.000.000: log₂(1.000.000) ≈ 20 langkah.

O(N) — Linear. Biaya tumbuh dengan input. Contoh: skanning linear dari daftar, membaca file, menghitung item dalam kumpulan. Pada N=10.000: 10.000 operasi.

O(N log N) — Linearithmic. Hampir linear, sedikit lebih buruk. Contoh: sortir merge, algoritma jalur terpendek (Dijkstra dengan heap). Pada N=10.000: ~133.000 operasi.

O(N²) — Kuadratik. Biaya meledak. Contoh: list.contains() dipanggil di dalam loop di atas daftar yang sama, sortir gelembung, perbandingan semua pasang yang sederhana. Pada N=1.000: 1.000.000 operasi. Pada N=10.000: 100.000.000 operasi.

O(2^N) — Ekspansif. Tidak bisa digunakan pada skala yang bermakna. Contoh: kombinatorik brute-force, menemukan semua subset. Pada N=30: lebih dari 1.000.000.000 operasi.

Skala yang Membuatnya Terlihat

N=10 perbandingan:
  O(N):   10
  O(N²):  100
  rasio:  10x

N=1.000 perbandingan:
  O(N):   1.000
  O(N²):  1.000.000
  rasio:  1.000x

N=10.000 perbandingan:
  O(N):   10.000
  O(N²):  100.000.000
  rasio:  10.000x

Pada N=10, perbedaan hampir tidak terdeteksi. Pada N=10.000, algoritma O(N²) berjalan 10.000 kali lebih lambat. Itulah mengapa MOAD-0001 tetap tidak terlihat selama dua dekade: grafik dependensi yang dijalankannya pada 1993 memiliki 50 node. Pada 2020, kode yang sama dijalankan pada grafik dependensi dengan 50.000 node.

Klasifikasikan Tiga Operasi

Terapkan kelas kompleksitas ke operasi konkret. Pertanyaan kunci untuk setiap: berapa operasi yang diperlukan saat N tumbuh?

Kode Benar, Kurva Pertumbuhan Salah

Kode benar yang menjalankan waktu O(N²) menghasilkan hasil yang sama dengan kode O(N). Tes lolos. Output cocok. Tidak ada pengecualian yang terbang. Defek tersembunyi dalam kurva pertumbuhan.

Sifat ini membuat kerusakan O(N²) berstratifikasi: mereka mengalami pengapungan di dalam kode yang berfungsi & hanya menjadi terlihat saat N melebihi batas ambang. Kode tidak berubah. Dunia di sekitarnya yang berubah.

MOAD-0001: Kerusakan Stratifikasi

Instansi yang paling luas: visited = [] di dalam loop perambatan graf.

visited = []
for node in graph:
    if node not in visited:  # O(N) scan setiap panggilan
        visited.append(node)
        process(node)

Setiap panggilan not in visited melakukan scan 0 hingga len(visited)-1 item. N panggilan × N/2 rata-rata item yang di-scan = O(N²) total. Perbaikan: satu baris.

visited = set()  # O(1) pengujian anggota
for node in graph:
    if node not in visited:  # O(1) pencarian hash
        visited.add(node)
        process(node)

Sama perilaku. Sama output. Sama tes yang lolos. Laik operasional mengubah laju pertumbuhan dari O(N²) menjadi O(N). Pada N=1.000: 1.000× lebih cepat. Pada N=10.000: 10.000× lebih cepat.

Mengapa Era Hamming Menyebabkan Ini

Pada awal Java & C, ArrayList (array dinamis) adalah container berurutan default. Set sudah ada tapi tidak idiomatik — para pengembang mencapai yang terasa familiar. Pada tahun 1993, perambatan graf dengan N=50 berjalan dalam mikrodetik dengan visited = []. Kode tersebut masuk ke sistem kontrol versi, salinan, diapit dalam library, dan dikirim melalui manajer paket. Pada tahun 2020, pola yang sama berjalan pada graf ketergantungan dengan 50.000 node.

Kode benar pada tahun 1993. Namun, menjadi mahal saat dunia di sekitarnya berubah. Era Hamming menanamkan kerusakan ini kelas dengan tidak menamai pertanyaan tentang laju pertumbuhan.

Diagnosa & Perbaikan

Terapkan diagnostik: cari pola O(N²), identifikasi perbaikan.

Apa Perubahan Nama

Sebelum Big O memiliki nama, programmer menyadari 'ini berjalan lambat.' Mereka profil. Mereka menulis ulang. Tapi mereka tidak bisa mengajarkan pola - mereka hanya bisa menunjuk ke contoh. Pola tanpa nama tidak dapat ditransfer.

Setelah Big O memiliki nama, seorang insinyur senior dapat mengatakan 'ini O(N²), gantilah dengan set' dan seorang insinyur junior dapat memahami, menerapkan, dan mengajarkan pola tersebut secara bergantian. Nama membuat pola menjadi satuan pengetahuan yang dapat ditransfer.

Hamming tahu dinamika ini di domain lain. Ia menjelaskan bagaimana penamaan 'spaghetti code' pada tahun 1960-an memungkinkan komunitas untuk mengenali, membahas, dan akhirnya menghilangkan kelas kegagalan yang semua orang telah mengalami tetapi tidak ada yang namai. Mekanisme yang sama berlaku untuk kelas kompleksitas.

Unhamming menambahkan vokabuler yang diabaikan oleh Hamming: O(1), O(log N), O(N), O(N log N), O(N²), O(2^N). Nama-nama ini memungkinkan Anda melihat kurva pertumbuhan dalam kode yang Anda baca, memprediksi kinerja skala, dan mengomunikasikan perbaikan dengan tepat. Mereka memenuhi tes Hamming sendiri untuk fundamental: berlangsung lama, dan menghasilkan sebagian besar bidang lain.

Dari Teori Bilangan ke Ilmu Komputer

Notasi Big O tidak berasal dari ilmu komputer. Ia berasal dari matematika murni - khususnya dalam teori bilangan - 74 tahun sebelum Donald Knuth mengadaptasinya untuk algoritma.

Paul Bachmann, 1894

Paul Bachmann, seorang matematikawan Jerman, memperkenalkan notasi O dalam bukunya Die Analytische Zahlentheorie (Teori Bilangan Analitik) pada tahun 1894. Ia membutuhkan cara yang padat untuk menyatakan bahwa satu kuantitas tumbuh tidak lebih cepat dari yang lain, hingga faktor konstan. Menulis 'f(n) = O(g(n))' mengatakan: f tumbuh paling banyak secepat g. Ini memungkinkan matematikawan teori bilangan untuk berpikir tentang istilah kesalahan dalam pendekatan tanpa mengikuti konstanta tepat.

Bachmann tidak berpikir tentang loop, struktur data, atau waktu eksekusi. Ia berpikir tentang sebaran bilangan prima - khususnya tentang istilah kesalahan dalam Teorema Bilangan Prima.

Edmund Landau, 1909

Edmund Landau, matematikawan Jerman lainnya, mempopulerkan notasi ini dalam bukunya Handbuch der Lehre von der Verteilung der Primzahlen (Pedoman tentang Distribusi Bilangan Prima) pada tahun 1909. Landau juga memperkenalkan notasi terkait o (kecil-o) dan menggunakan keluarga simbol asimptotik secara luas sehingga keluarga ini dikenal sebagai notasi Bachmann-Landau atau sederhananya notasi Landau.

Untuk enam dasawarsa, notasi O hidup sepenuhnya di bidang matematika. Tidak satu pun programmer yang memikirkannya.

Donald Knuth, 1968 & 1976

Donald Knuth menerjemahkan notasi ke dalam ilmu komputer. Dalam The Art of Computer Programming (Vol. 1, 1968), Knuth menggunakan notasi O untuk mendeskripsikan waktu jalannya algoritma — langsung menanamkan alat Bachmann ke domain baru. Dia adalah orang pertama yang secara sistematis menerapkannya untuk analisis algoritma.

Pada tahun 1976, Knuth menerbitkan sebuah artikel singkat di SIGACT News dengan judul 'Big Omicron and Big Omega and Big Theta'. Dia memperkenalkan Omega (Omega) untuk batas bawah dan Theta untuk batas ketat, menyelesaikan vokabuler tiga simbol yang digunakan ilmu komputer saat ini. Dia juga berargumen untuk mengstandarkan penggunaan simbol-simbol ini di bidang tersebut — sebuah tindakan penguat standardisasi yang mempercepat pengadopsian.

Pada awal tahun 1980-an, Big O muncul dalam setiap buku teks algoritma. Pada tahun 1990-an, itu menjadi vocabulary wawancara standar.

Perjalanan 74 Tahun

1894 — Bachmann memperkenalkan O dalam teori bilangan
1909 — Landau mempopulerkan O, o, dan keluarga notasi penuh
1953 — Hamming memulai penelitian di Bell Labs (tetap tidak belajar Big O sebagai alat CS)
1968 — Knuth menerapkan O pada analisis algoritma di TAOCP Vol. 1
1976 — Knuth menambahkan Omega dan Theta; berargumen untuk standarisasi
1980-an — Big O masuk semua kurikulum CS
1993 — MOAD-0001 lapisan sedimentasi terbentuk dalam kode produksi
1995 — Hamming mengajar versi terakhir kursusnya; tidak pernah menutupi Big O
2026 — MOAD-0001 ditemukan dalam 1.000+ proyek sumber terbuka

Alat Bachmann menghabiskan 74 tahun di matematika murni, terlihat oleh setiap matematikawan tapi tidak terlihat oleh setiap programmer. Knuth melihat tanaman. Hamming — bekerja di era yang sama, bekerja sama dengan komunitas komputasi yang sama — tidak membuatnya bagian dari kelasnya.

Mengapa Standarisasi Knuth Penting

Paparan Knuth tahun 1976 melakukan lebih dari sekadar memperkenalkan Omega dan Theta. Dia berargumen bahwa bidang ini membutuhkan notasi konsisten, dan bahwa notasi tidak konsisten aktif merugikan. Buku teks berbeda menggunakan O untuk berarti hal yang berbeda — terkadang sebagai batas atas, terkadang sebagai pendekatan, terkadang tanpa menentukan apakah konstan penting. Knuth membersihkan ini.

Ini adalah pola penamaan dinamis Hamming yang diterapkan pada notasi itu sendiri. Sebelum Knuth mengstandardisir simbol-simbol tersebut, para insinyur tidak dapat dengan tepat menyampaikan klaim kompleksitas melintasi buku teks, kertas, atau tim. Setelah standarisasi, 'ini berjalan dengan O(N log N)' memiliki arti yang tepat tanpa peduli siapa pun yang mengatakannya.

Knuth juga menyumbang terjemahan informal: 'O(f(n)) berarti waktu jalannya program adalah paling banyak konstan kali f(n), untuk semua nilai n yang cukup besar.' Interpretasi ini - batas atas, hingga faktor konstan, untuk input yang besar - menjadi intuisi standar yang dipelajari setiap programmer.