Catatan Tutorials

Algoritma dan Big-O tanpa matematika rumit

Kenapa ada kode yang makin lambat saat datanya membesar dan ada yang tidak. Apa itu algoritma, bagaimana Big-O menggambarkan pertumbuhan, beberapa kelas yang benar-benar akan Anda temui, dan pengukuran nyata yang menunjukkan bedanya.

6 menit bacaTersedia juga dalam bahasa Inggris →

Dua bagian sebelumnya meninggalkan janji. Di bagian 6, fungsi Fibonacci dipanggil 242.785 kali padahal 26 kali sudah cukup. Di bagian 8, mengecek di set sekitar 46.000 kali lebih cepat daripada mengecek di list. Komputernya sama dua-duanya. Yang berubah adalah algoritmanya. Bagian ini menjelaskan alasannya, tanpa matematika yang lebih rumit dari menggandakan sebuah angka.

Apa itu algoritma

Algoritma adalah “any well-defined set of instructions that when followed terminates after a finite number of steps that comprise a solution to a given computational problem”: serangkaian instruksi yang jelas, yang kalau diikuti akan selesai dalam jumlah langkah terbatas dan menghasilkan jawaban. Semacam resep untuk mendapat jawaban.

Satu masalah biasanya punya beberapa algoritma. “Apakah angka ini ada di kumpulan data?” bisa dijawab dengan mengecek semua item, dengan melompat ke tengah list yang sudah terurut, atau dengan bertanya ke set. Ketiganya benar. Bedanya ada di berapa banyak kerja yang dilakukan, dan yang lebih penting, bagaimana kerja itu bertambah saat datanya bertambah.

Big-O: bagaimana kerja bertambah

Mengukur kecepatan dalam detik bergantung pada mesin, bahasa, dan apa lagi yang sedang berjalan. Jadi kita ajukan pertanyaan yang lebih sederhana: kalau inputnya jadi dua kali lipat, apa yang terjadi pada kerjanya?

Itulah yang digambarkan notasi Big-O. Wikipedia: “In computer science, big O notation is used to classify algorithms by how their run time or space requirements grow with the input.” Dokumentasi Python memakainya dengan cara yang sama: “to describe how the running time of an operation grows with the size of its inputs.”

O(n) dibaca “orde n”, dengan n adalah ukuran input. Beberapa aturan membuatnya tetap sederhana:

  • Hanya pertumbuhannya yang penting. O(2n) dan O(n) dianggap sama; konstanta dibuang.
  • Hanya bagian terbesarnya yang penting. O(n² + n) cukup ditulis O(n²), karena untuk n besar bagian n² yang mendominasi.
  • Biasanya menggambarkan kasus terburuk, kecuali disebutkan lain.

Kelas yang benar-benar akan Anda temui

Big-O Nama Kalau input jadi 2× lipat… Contoh sehari-hari
O(1) konstan kerjanya tetap mengambil kunci di dict, set, atau map
O(log n) logaritmik bertambah satu langkah binary search di list terurut
O(n) linear kerjanya jadi 2× menelusuri setiap item sekali
O(n log n) linearitmik sedikit lebih dari 2× algoritma sorting yang baik
O(n²) kuadratik kerjanya jadi 4× loop di dalam loop atas data yang sama
O(2ⁿ) eksponensial kerjanya dikuadratkan (kira-kira) Fibonacci naif, mencoba semua kombinasi

Dokumentasi Python mencantumkan angka-angka ini untuk operasi bawaan. Beberapa barisnya: untuk list, x in l adalah O(n); untuk set, x in s adalah O(1); untuk dict, mengambil item adalah O(1); mengurutkan list adalah O(n log n). Angka dict adalah rata-rata, yang “assume the hash function for the objects is sufficiently robust to make collisions uncommon”, tapi di kode sehari-hari asumsi itu terpenuhi.

Melihatnya langsung: kuadratik vs linear

Tugas yang umum: apakah sebuah list berisi duplikat? Percobaan pertama membandingkan setiap item dengan setiap item lainnya:

def has_duplicate_nested(items):
    for i in range(len(items)):
        for j in range(i + 1, len(items)):
            if items[i] == items[j]:
                return True
    return False

Loop di dalam loop atas data yang sama: O(n²). Dengan set dari bagian 8, setiap item cukup dicek sekali:

def has_duplicate_set(items):
    seen = set()
    for x in items:
        if x in seen:
            return True
        seen.add(x)
    return False

Satu kali lewat dengan pengecekan O(1): O(n). Mengukur keduanya pada list tanpa duplikat (kasus terburuk, karena keduanya harus melihat semua item), di mesin yang dipakai untuk menulis catatan ini:

     n  nested (s)    set (s)
  1000      0.0093   0.000023
  2000      0.0370   0.000045
  4000      0.1537   0.000091
  8000      0.6056   0.000237

Perhatikan apa yang terjadi setiap kali n jadi dua kali lipat. Versi set kira-kira jadi 2×: itu linear. Versi bersarang kira-kira jadi 4×: 0,009, 0,037, 0,154, 0,606. Itu kuadratik. Di 8.000 item sudah lebih dari setengah detik; di 80.000 item akan sekitar 100 kali lebih lambat lagi, kira-kira satu menit, sementara versi set masih selesai dalam beberapa milidetik.

Karena itulah solusi O(n²) bisa lolos semua tes dengan 20 baris data, lalu timeout di production dengan 50.000 baris.

Gagasan yang sama di PHP: in_array mencari item satu per satu (O(n)), sedangkan isset pada kunci array adalah pencarian langsung. Membalik array sekali dengan array_flip mengubah nilai menjadi kunci:

$ids = range(1, 1_000_000);
$lookup = array_flip($ids);

in_array(999_999, $ids);      // ×100 → 0.0967 s
isset($lookup[999_999]);      // ×100 → 0.000008 s

Melihatnya langsung: logaritmik

Binary search bekerja pada data yang sudah terurut. Ia “compares the target value to the middle element of the array”, membandingkan target dengan elemen tengah, lalu membuang separuh bagian yang tidak mungkin berisi target, dan mengulanginya. Menghitung langkah untuk menemukan item terakhir:

binary search in 1,000 items: 10 steps
binary search in 1,000,000 items: 20 steps
binary search in 1,000,000,000 items: 30 steps

Data seribu kali lebih banyak, langkahnya hanya bertambah sepuluh. Itulah O(log n), dan karena itulah “Binary search runs in logarithmic time in the worst case.” Modul bisect di Python mengerjakannya untuk Anda; ia “provides support for maintaining a list in sorted order without having to sort the list after each insertion”:

import bisect
prices = [5, 12, 30, 45]
i = bisect.bisect_left(prices, 30)
print(i, prices[i] == 30)   # 2 True

Syaratnya: data harus diurutkan dulu, dan menjaganya tetap terurut ada ongkosnya. Dokumentasi bisect jujur soal ini: “the O(log n) search is dominated by the slow O(n) insertion step”, pencariannya cepat tapi penyisipannya lambat. Pertukaran seperti ini umum: pencarian yang lebih cepat biasanya dibayar saat menyisipkan data atau dengan memori.

Sorting: biasanya bukan urusan Anda

Sorting serbaguna yang baik itu O(n log n), dan hampir tidak pernah perlu menulis sendiri. Python memakai Timsort, yang “can take advantage of any ordering already present in a dataset”, dan “Sorts are guaranteed to be stable”, artinya “when multiple records have the same key, their original order is preserved”: data dengan kunci sama tetap pada urutan aslinya. Array.prototype.sort di JavaScript, sort di PHP, dan slices.Sort di Go semuanya bawaan dan sudah teruji. Pakai saja.

Memori juga dihitung

Big-O juga menggambarkan memori. Cek duplikat versi set lebih cepat karena menyimpan set berisi semua yang sudah dilihat, yang memakan memori tambahan O(n). Versi bersarang hampir tidak memakai memori tambahan. Memoization di bagian 6 adalah pertukaran yang sama: mengingat jawaban (memori) supaya tidak menghitung ulang (waktu). Kebanyakan perbaikan performa adalah tawar-menawar antara keduanya.

Cara memakainya tanpa berhitung

Anda jarang perlu menghitung Big-O secara formal. Yang perlu adalah mengenali polanya:

  • Loop di dalam loop atas data yang sama → kemungkinan O(n²). Tanyakan apakah set atau map bisa menggantikan loop bagian dalam.
  • Mencari di list di dalam loop (if x in some_list di dalam for) → masalah yang sama dalam bentuk lain.
  • Fungsi yang memanggil dirinya dua kali per pemanggilan dengan kerja yang tumpang tindih → mungkin eksponensial. Pikirkan memoization.
  • Memanggil database atau API di dalam loop → pola yang sama, tapi tiap langkah makan milidetik, bukan nanodetik. Ambil semua yang dibutuhkan dalam satu query.
  • Mengurutkan hanya untuk mencari nilai terkecil atau terbesar → min() / max() itu O(n), sorting O(n log n).

Dan aturan paling penting: ukur dulu sebelum mengoptimasi. Big-O memberi tahu bagaimana kode akan berperilaku saat data membesar; pengukuran singkat memberi tahu apakah itu penting di ukuran data Anda yang sebenarnya. Loop O(n²) yang jelas atas 50 item tidak masalah.

Kenapa ini penting sehari-hari

  • Kode yang lancar saat testing tapi tumbang di production sering kali adalah O(n²) yang bersembunyi di balik data tes yang kecil.
  • Laporan dan ekspor adalah tempat masalah ini paling sering muncul: mencocokkan pesanan ke pelanggan, produk ke stok, baris ke baris.
  • Query database di dalam loop adalah pola yang sama dengan ongkos per langkah yang jauh lebih mahal.
  • Memilih struktur data berarti memilih algoritma. Kebanyakan perbaikan adalah “pakai map/set alih-alih mencari di list”.

Coba sendiri

  1. Jalankan sendiri pengukuran cek duplikat dan tambahkan n = 16000. Tebak kedua angkanya sebelum menjalankan.
  2. Hitung berapa langkah binary search untuk menemukan sebuah item di antara 1.000.000.000.000 item. Lalu cek dengan kodenya.
  3. Cari loop bersarang di kode Anda sendiri. Apakah loop bagian dalamnya mencari sesuatu yang bisa langsung diambil dari map?
  4. Tulis fungsi yang mengembalikan angka terbesar kedua di sebuah list dalam O(n), tanpa sorting.

Ringkasan

  • Algoritma adalah cara yang jelas dan terbatas untuk menyelesaikan masalah; satu masalah biasanya punya beberapa algoritma.
  • Big-O menggambarkan bagaimana kerja bertambah seiring bertambahnya input, tanpa konstanta dan suku yang lebih kecil.
  • Kelas yang umum: O(1), O(log n), O(n), O(n log n), O(n²), O(2ⁿ).
  • Hasil pengukuran: input 2× lipat membuat versi linear 2× lebih lama dan versi kuadratik 4× lebih lama.
  • Binary search di data terurut: item 1.000× lebih banyak, hanya 10 langkah lebih.
  • Kenali polanya (loop bersarang, pencarian di dalam loop, query di dalam loop), lalu ukur sebelum mengoptimasi.

Referensi