Seberapa cepat? Notasi Big O

Dengan satu miliar langkah per detik, metode n² pada sejuta nilai butuh sekitar 17 menit; metode n log n hanya 0.02 detik.

Pertumbuhan lebih penting daripada hitungan tepatnya

Sejauh ini kita menghitung langkah secara tepat: 45 perbandingan, 4 pertukaran, 20 pemeriksaan. Hitungan tepat berguna untuk contoh kecil, tetapi bergantung pada detail seperti apakah bubble sort berhenti lebih awal atau bagaimana pivot dipilih. Saat masukannya menjadi besar, satu hal mengalahkan semua yang lain: bagaimana hitungan itu tumbuh seiring bertambahnya n. Algoritma yang langkahnya tumbuh seperti n² pada akhirnya akan kalah dari algoritma yang langkahnya tumbuh seperti n log n, betapa pun cermatnya algoritma pertama disetel.

Notasi Big O adalah singkatan untuk pertumbuhan itu. Menulis bahwa sebuah algoritma O(n²), dibaca "big O dari n kuadrat", berarti untuk n yang besar jumlah langkahnya paling banyak suatu konstanta dikali n². Dua aturan membuatnya mudah dipakai. Buang faktor konstanta: 3n dan n/2 sama-sama O(n). Pertahankan hanya suku yang tumbuh paling cepat: n²/2 − n/2, jumlah perbandingan selection sort, adalah O(n²), karena untuk n yang besar bagian n² hampir mencakup semuanya. Mata kuliah 6.006 di MIT memakai gagasan yang sama saat membandingkan struktur data dan algoritma pengurutan menurut waktu jalan asimptotiknya.

Laju pertumbuhan yang umum

• O(1), konstan. Pekerjaannya tidak bergantung pada n: membaca nilai pertama dalam daftar, atau nilai di posisi yang sudah diketahui.
• O(log n), logaritmik. Setiap langkah membagi dua masalahnya: pencarian biner. Sejuta nilai, sekitar 20 langkah.
• O(n), linear. Setiap nilai ditangani satu kali: pencarian linear, mencari nilai terbesar, menjumlahkan isi daftar.
• O(n log n). Merge sort, dan quicksort secara rata-rata. Yang terbaik yang bisa dicapai pengurutan berbasis perbandingan.
• O(n²), kuadratik. Setiap pasangan diperiksa: bubble sort, selection sort, dan insertion sort dalam kasus terburuk, atau dua perulangan yang bersarang satu di dalam yang lain.
• O(2ⁿ), eksponensial. Pekerjaannya berlipat dua untuk setiap nilai tambahan: mencoba setiap himpunan bagian dari n benda, atau memindahkan n cakram dalam Menara Hanoi.

Arti angka-angka itu dalam detik

Misalkan sebuah komputer melakukan satu miliar (10⁹) langkah dasar per detik, angka bulat yang wajar untuk satu inti prosesor. Inilah arti setiap laju pertumbuhan untuk sejuta nilai. O(log n) sekitar 20 langkah, jauh di bawah satu mikrodetik. O(n) sejuta langkah, satu milidetik. O(n log n) sekitar 20 juta langkah, 0.02 detik. O(n²) adalah 10¹² langkah, seribu detik, sekitar 17 menit. O(2ⁿ) tidak bisa selesai: 2 pangkat sejuta adalah bilangan dengan lebih dari 300 000 angka. Karena itulah memilih algoritma yang tepat biasanya jauh lebih penting daripada membeli komputer yang lebih cepat. Mesin sepuluh kali lebih cepat mengubah 17 menit menjadi 1.7 menit; beralih dari O(n²) ke O(n log n) mengubahnya menjadi seperlima puluh detik.

Membaca Big O dari kode

Laju pertumbuhan sering bisa dibaca langsung dari bentuk kodenya. Satu perulangan atas daftar adalah O(n). Dua perulangan, satu di dalam yang lain, keduanya atas daftar, adalah O(n²): untuk setiap putaran dari n putaran luar, perulangan dalam melakukan paling banyak n putaran. Perulangan yang membagi dua sebuah bilangan setiap kali, seperti while (n > 1) n = Math.floor(n / 2), adalah O(log n): mulai dari 1000 perulangan itu berjalan 9 kali, dari sejuta 19 kali. Langkah-langkah yang terjadi berurutan dijumlahkan, dan suku yang lebih besar menang: perulangan O(n) yang diikuti perulangan O(n²) secara keseluruhan adalah O(n²).

// O(n): satu lintasan
let total = 0;
for (const x of list) total += x;

// O(n²): setiap pasangan
for (let i = 0; i < list.length; i++)
  for (let j = i + 1; j < list.length; j++)
    if (list[i] === list[j]) console.log("duplicate", list[i]);

// O(log n): membagi dua
let k = list.length, rounds = 0;
while (k > 1) { k = Math.floor(k / 2); rounds++; }

Kasus terbaik, rata-rata, dan terburuk

Satu algoritma bisa berperilaku sangat berbeda pada masukan yang berbeda. Insertion sort adalah O(n) pada daftar yang sudah terurut dan O(n²) pada daftar terbalik. Quicksort adalah O(n log n) secara rata-rata dan O(n²) kalau pivotnya terus-menerus buruk. Ketika orang menyebut satu angka Big O tanpa menyebut kasusnya, biasanya yang dimaksud kasus terburuk, karena itu sebuah jaminan: algoritmanya tidak akan pernah lebih buruk dari itu. Big O juga mengabaikan beberapa hal. Faktor konstanta diabaikan, jadi untuk masukan kecil, metode O(n²) dengan langkah yang sangat sederhana bisa mengalahkan metode O(n log n). Itulah sebabnya banyak rutin pengurutan sungguhan beralih ke insertion sort untuk potongan daftar yang pendek.