Notasi Big O — Kompleksitas Waktu Dijelaskan Sederhana

Notasi Big O memberi tahu seberapa cepat waktu jalan atau penggunaan memori suatu algoritma dapat bertambah saat ukuran input membesar. Jika Anda bertanya, "Apa yang terjadi ketika masalah menjadi jauh lebih besar?", Big O adalah cara standar untuk menjawabnya.

Itulah sebabnya orang mengatakan pencarian linear adalah $O(n)$ dan pencarian biner adalah $O(\log n)$. Tujuannya bukan untuk memprediksi milidetik yang tepat pada satu mesin. Tujuannya adalah membandingkan pola pertumbuhan.

Apa Arti Big O

Jika suatu algoritma membutuhkan waktu $T(n)$ pada input berukuran $n$, maka

$$T(n) = O(f(n))$$

berarti bahwa untuk beberapa konstanta $C > 0$ dan $n_0$,

$$T(n) \le C f(n) \quad \text{for all } n \ge n_0$$

Ini menyatakan bahwa Big O adalah pernyataan batas atas tentang pertumbuhan untuk input yang cukup besar.

Dalam bahasa sederhana: setelah $n$ cukup besar, runtime tidak bertambah lebih cepat daripada kelipatan konstan dari $f(n)$.

Mengapa Big O Berguna

Big O memberi cara yang tidak bergantung pada mesin untuk membandingkan algoritma. Sebuah program mungkin berjalan lebih cepat di satu laptop daripada di laptop lain, tetapi tren pertumbuhannya tetap penting.

Tren itu paling penting ketika ukuran input berubah sangat banyak. Algoritma yang masih baik untuk $100$ item bisa menjadi tidak praktis untuk $10^6$ item jika laju pertumbuhannya buruk.

Kompleksitas Waktu yang Umum Sekilas

• $O(1)$: jumlah kerja tetap terbatas saat $n$ bertambah.
• $O(\log n)$: jumlah kerja bertambah lambat, sering muncul ketika ukuran masalah terus diperkecil.
• $O(n)$: jumlah kerja bertambah kira-kira sebanding dengan ukuran input.
• $O(n \log n)$: sedikit lebih dari linear, umum pada pengurutan yang efisien.
• $O(n^2)$: jumlah kerja bertambah seperti kuadrat ukuran input, sering berasal dari loop bersarang pada data yang sama.

Label ini membandingkan pertumbuhan, bukan kecepatan yang tepat. Algoritma $O(n)$ tetap bisa lebih lambat daripada algoritma $O(n^2)$ untuk input kecil jika faktor konstantanya besar.

Contoh: Mengapa Pencarian Linear Adalah $O(n)$

Misalkan Anda memindai sebuah daftar dari kiri ke kanan untuk mencari nilai target. Dalam kasus terburuk, target tidak ada atau berada di paling akhir, sehingga Anda mungkin perlu memeriksa setiap item satu kali.

Jika daftar memiliki $n$ item, jumlah pemeriksaan paling banyak adalah $n$. Itulah sebabnya waktu kasus terburuknya adalah

$$O(n)$$

Inti pentingnya sederhana: jika ukuran daftar menjadi dua kali lipat, jumlah pemeriksaan pada kasus terburuk juga bisa kira-kira menjadi dua kali lipat. Itulah pola yang ditangkap oleh Big O.

Apa yang Tidak Dicakup Big O

Big O dengan sengaja mengabaikan faktor konstan dan suku berorde lebih rendah saat membandingkan pertumbuhan untuk input besar.

Sebagai contoh, jika

$$T(n) = 3n + 2$$

maka $T(n)$ tetap merupakan $O(n)$. Konstanta $3$ dan tambahan $2$ penting untuk waktu yang tepat, tetapi tidak mengubah pola pertumbuhan utamanya.

Itu tidak berarti konstanta tidak pernah penting dalam praktik. Artinya, Big O menjawab pertanyaan yang lebih sempit: bagaimana biaya bertambah saat $n$ menjadi besar.

Kesalahan Umum tentang Big O

Kesalahan 1: Menganggap Big O sebagai runtime yang tepat

$O(n)$ tidak berarti runtime-nya tepat $n$ langkah. Artinya, pertumbuhannya dibatasi dari atas oleh kelipatan konstan dari $n$ setelah $n$ cukup besar.

Kesalahan 2: Melupakan syarat $n$ besar

Definisi formalnya hanya perlu berlaku untuk semua $n \ge n_0$. Big O membahas perilaku asimtotik, bukan setiap input yang sangat kecil.

Kesalahan 3: Menganggap Big O selalu berarti runtime yang tipikal

Dalam pembahasan algoritma, Big O sering menggambarkan waktu kasus terburuk, tetapi itu adalah konvensi yang bergantung pada konteks. Kompleksitas rata-rata dan kasus terbaik adalah pertanyaan yang berbeda dan harus diberi label dengan jelas.

Kesalahan 4: Membandingkan algoritma hanya berdasarkan Big O

Big O itu penting, tetapi penggunaan memori, biaya implementasi, dan faktor konstan juga bisa sangat berpengaruh dalam sistem nyata.

Di Mana Anda Menemui Notasi Big O

Big O muncul dalam ilmu komputer, matematika diskret, dan analisis performa. Ini sangat berguna saat membandingkan algoritma untuk pencarian, pengurutan, penelusuran graf, dan dynamic programming.

Secara lebih luas, notasi ini digunakan kapan pun Anda peduli pada bagaimana suatu proses bertambah skala, bukan hanya bagaimana perilakunya pada satu ukuran tetap.

Coba Contoh Serupa

Ambil loop bersarang sederhana yang berjalan pada grid berukuran $n \times n$. Hitung berapa kali aksi di bagian dalam dijalankan. Jika total pekerjaannya bertambah seperti $n^2$, Anda punya contoh konkret mengapa loop berulang pada data yang sama sering menghasilkan perilaku $O(n^2)$.