Bagaimana Struktur Kode Mengungkapkan Kompleksitas

Cara Mengidentifikasi Big O dari Kode

Big O tersembunyi dalam bentuk kode Anda. Empat pola mencakup sebagian besar kasus:

Loop tunggal di atas N item: O(N)

# O(N): one pass through the list
for item in list_of_n_items:
    process(item)

Loop bersarang, masing-masing di atas N item: O(N²)

# O(N²): every item paired with every other item
for item_a in list_of_n_items:
    for item_b in list_of_n_items:
        compare(item_a, item_b)

Pencarian waktu konstan: O(1)

Akses indeks array, pencarian hash table — satu langkah terlepas dari ukuran.

Bagi-dan-taklukkan (potong masalah menjadi dua setiap langkah): O(log N)

Pencarian biner: setiap pemeriksaan membagi dua item yang tersisa.

---

Tersembunyi O(N²): daftar di dalam loop

# This looks like O(N) but it is actually O(N²)
visited = []
for item in list_of_n_items:
    if item not in visited:   # memindai semua yang dikunjungi: O(N)
        visited.append(item)  # seluruh loop: O(N²)

Baris if item not in visited memindai setiap elemen visited setiap iterasi. Pemindaian daftar memerlukan biaya O(N). Loop yang berjalan N kali, masing-masing melakukan pekerjaan O(N): O(N) × O(N) = O(N²).

Pola ini muncul di 1.000+ proyek open-source. Perbaikannya membutuhkan satu karakter: ganti visited = [] dengan visited = set(). Pengujian keanggotaan set memerlukan biaya O(1), bukan O(N). Satu perubahan. Hasil yang sama. 1.000× lebih cepat pada N=1.000.

Klasifikasi & Perbaiki Kode Ini

Baca kode ini:

result = []
for name in student_names:
    if name not in result:
        result.append(name)

Teori Bertemu Praktik

Big O di Alam Liar

Big O bukan hanya teori. Ini memisahkan program yang selesai dalam beberapa detik dari program yang membutuhkan 17 menit — pada tugas yang sama persis.

Contoh nyata: deteksi siklus dependensi dalam sistem pembangunan.

Ketika Anda menginstal perangkat lunak, komputer Anda menyelesaikan grafik dependensi: paket A memerlukan B, B memerlukan C, dan seterusnya. Sistem pembangunan memeriksa grafik ini untuk siklus.

Algoritma deteksi siklus O(N²) berfungsi baik pada paket N=100. Pada paket N=50.000 (proyek nyata): membutuhkan waktu 17 menit. Perbaikan O(N): 10 detik.

Cacat yang persis ini ada di GHC (kompiler Haskell), pip (pengelola paket Python), Maven (sistem pembangunan Java), Cargo (pengelola paket Rust), & 1.000+ proyek lainnya.

Bukan karena penulis mereka ceroboh. visited = [] ditulis ketika N kecil. Kode mengeras. N tumbuh. Tidak ada yang memperhatikan sampai pembangunan membutuhkan waktu setengah jam.

Big O adalah kosakata yang memungkinkan Anda untuk menamai apa yang terjadi — & memperbaikinya.

---

Ingin menggali lebih dalam? Kursus unhamming kami mencakup bab lengkap tentang Big O, MOAD-0001 (cacat O(N²) nyata yang ditemukan di 1.000+ proyek open-source), & mengapa penamaan pola memungkinkan Anda menemukannya di mana-mana. Lihat Bab yang Hilang: Kompleksitas Algoritma.

Prediksi Waktu Pembangunan

Sistem pembangunan menggunakan deteksi siklus O(N²).

Waktu pembangunan terukur:

- N=100 paket: 0,01 detik

- N=1.000 paket: 1 detik

Untuk O(N²): waktu berkala sebagai (N_new / N_old)².

Untuk O(N): waktu berkala sebagai (N_new / N_old).