Laju Pertumbuhan, Bukan Biaya Absolut
Big O: Mengukur Bagaimana Biaya Tumbuh
Notasi Big O mengukur laju pertumbuhan biaya algoritma — bukan biaya absolut.
Pertanyaan Big O: apakah pekerjaan menggandakan, empat kali lipat, atau tetap flat saat ukuran input N menggandakan?
Huruf 'O' berasal dari 'order of magnitude.' Ekspresi di dalam tanda kurung menggambarkan bentuk kurva pertumbuhan.
Kelas kompleksitas:
- O(1) — konstan: biaya tidak tumbuh. Contoh: mencari nilai dengan indeks dalam array. Apakah array memiliki 10 item atau 10 juta, satu pencarian tetap satu pencarian.
- O(N) — linear: biaya tumbuh dengan input. Contoh: membaca setiap item dalam daftar sekali. Dua kali lipat daftar, dua kali lipat bacaan.
- O(N²) — kuadrat: biaya tumbuh sebagai kuadrat dari input. Contoh: membandingkan setiap item dengan setiap item lainnya. Dua kali lipat N, empat kali lipat pekerjaan.
Tabel perbandingan pertumbuhan:
| N | O(1) | O(N) | O(N²) |
|---|------|------|-------|
| 10 | 1 | 10 | 100 |
| 100 | 1 | 100 | 10,000 |
| 1,000 | 1 | 1,000 | 1,000,000 |
Pada N=10 perbedaan tampak kecil. Pada N=1,000 jarak menjadi besar.
Bandingkan O(N) dengan O(N²)
Gunakan tabel perbandingan pertumbuhan di atas.
Pada N=1,000: O(N) membutuhkan 1,000 operasi. O(N²) membutuhkan 1,000,000 operasi.
Bagaimana Struktur Kode Menunjukkan Kemudahan
Bagaimana Cara Mengidentifikasi Big O dari Kode
Big O tersembunyi dalam bentuk kode Anda. Empat pola menutupi sebagian besar kasus:
Pengulangan tunggal melalui N item: O(N)
# O(N): satu kali melalui daftar
for item in list_of_n_items:
process(item)Pengulangan bergandengan, masing-masing melalui N item: O(N²)
# O(N²): setiap item dipair dengan setiap item lainnya
for item_a in list_of_n_items:
for item_b in list_of_n_items:
compare(item_a, item_b)Pencarian konstan: O(1)
Akses indeks array, pencarian dalam tabel hash — satu langkah terlepas dari ukuran.
Membagi dan menaklukkan (memotong masalah menjadi setengah setiap langkah): O(log N)
Pencarian biner: setiap cek mengurangi jumlah item yang tersisa.
---
O(N² tersembunyi): daftar di dalam loop
# Ini terlihat seperti O(N) tetapi sebenarnya O(N²)
visited = []
for item in list_of_n_items:
if item not in visited: # memindai semua dari visited: O(N)
visited.append(item) # loop keseluruhan: O(N²)Baris if item not in visited memindai setiap elemen dari visited setiap iterasi. Scan daftar menghabiskan O(N). Sebuah loop yang berjalan N kali, setiap melakukan O(N) kerja: O(N) × O(N) = O(N²).
Polanya muncul di 1.000+ proyek sumber terbuka. Perbaikan hanya membutuhkan satu karakter: gantilah visited = [] dengan visited = set(). Tes anggota setelan menghabiskan O(1), bukan O(N). Perubahan satu. Hasil yang sama. 1.000× lebih cepat pada N=1.000.
Klasifikasi & Perbaikan Kode Ini
Baca kode ini:
result = []
for name in student_names:
if name not in result:
result.append(name)Teori Bertemu Dengan Praktek
Big O di Dunia Nyata
Big O tidak hanya teori. Ini memisahkan program yang selesai dalam detik dari program yang membutuhkan 17 menit - pada tugas yang sama persis.
Contoh nyata: deteksi siklus ketergantungan dalam sistem build.
Ketika Anda menginstal perangkat lunak, komputer Anda menyelesaikan grafik ketergantungan: paket A membutuhkan B, B membutuhkan C, dan seterusnya. Sistem build mengecek grafik ini untuk siklus.
Algoritma deteksi siklus O(N²) berfungsi baik pada N=100 paket. Pada N=50,000 paket (proyek nyata): itu membutuhkan 17 menit. Perbaikan O(N): 10 detik.
Defek ini persis ada dalam GHC (kompiler Haskell), pip (manajer paket Python), Maven (sistem build Java), Cargo (manajer paket Rust), & 1.000+ proyek lainnya.
Bukan karena penulisnya tidak teliti. visited = [] ditulis ketika N kecil. Kode mengeras. N tumbuh. Tidak ada yang melihat sampai build memakan setengah jam.
Big O adalah bahasa yang memungkinkan Anda menamai apa yang terjadi - & memperbaikinya.
---
Ingin menggali lebih dalam? Kursus Unhamming kami mencakup bab penuh tentang Big O, MOAD-0001 (defek O(N²) nyata yang ditemukan di 1.000+ proyek sumber terbuka), & mengapa menamai pola memungkinkan Anda menemukannya di mana-mana. Lihat [Bab yang Hilang: Kompleksitas Algoritma](/en/un/unhamming_algorithmic_complexity).
Prediksi Waktu Build
Sistem build menggunakan deteksi siklus O(N²).
Waktu build yang diukur:
- N=100 paket: 0.01 detik
- N=1,000 paket: 1 detik
Untuk O(N²): waktu berkorespondensi dengan (N_new / N_old)².
Untuk O(N): waktu berkorespondensi dengan (N_new / N_old).