Cara Menghitung Big O dari Kode: Loop Bersarang sampai Log n

Big O dari sebuah kode dihitung dengan cara menghitung berapa kali operasi paling dalam dijalankan sebagai fungsi dari $n$ , lalu membuang konstanta dan suku yang tumbuhnya lebih lambat. Loop berurutan dijumlahkan, loop bersarang dikalikan, dan loop yang variabelnya dikali atau dibagi 2 menghasilkan $\log n$ . Delapan contoh soal di bawah melatih ketiga aturan itu, masing-masing dengan jumlah iterasi yang bisa kamu cek sendiri.

Tiga aturan dasarnya:

Berurutan dijumlah. Dua blok yang ditulis satu setelah yang lain memakan $f (n) + g (n)$ langkah. Ambil yang terbesar.
Bersarang dikali. Loop di dalam loop memakan (iterasi luar) kali (iterasi dalam), asalkan loop dalam tidak bergantung pada variabel luar. Kalau bergantung, jumlahkan satu per satu.
Buang konstanta dan suku kecil. $3 n^{2} + 5 n + 2$ ditulis $O (n^{2})$ . Konstanta 3 dan suku $5 n$ tidak mengubah bentuk pertumbuhan.

Contoh di bawah memakai Python, tapi logikanya sama untuk C, Java, atau pseudocode. Yang dihitung adalah berapa kali baris c += 1 dijalankan.

#Soal 1 sampai 4: loop tunggal, berurutan, dan bersarang

#Soal 1. Loop tunggal

for i in range(n):
    c += 1

Badan loop jalan tepat $n$ kali. Jawaban: $O (n)$ . Kalau loopnya range(0, n, 2), iterasinya $⌈ n / 2 ⌉$ (untuk $n$ genap tepat $n / 2$ ), dan tetap $O (n)$ karena faktor $\frac{1}{2}$ adalah konstanta.

#Soal 2. Dua loop berurutan

for i in range(n):
    c += 1
for j in range(n):
    c += 1

Totalnya $n + n = 2 n$ langkah. Jawaban: $O (n)$ , bukan $O (n^{2})$ . Dua loop yang tidak bersarang tidak dikalikan.

#Soal 3. Bersarang penuh

for i in range(n):
    for j in range(n):
        c += 1

Untuk setiap $i$ , loop dalam jalan $n$ kali. Totalnya $n \cdot n = n^{2}$ . Jawaban: $O (n^{2})$ .

#Soal 4. Bersarang segitiga

for i in range(n):
    for j in range(i):
        c += 1

Loop dalam bergantung pada $i$ , jadi tidak bisa langsung dikali. Saat $i = 0$ loop dalam jalan 0 kali, saat $i = 1$ jalan 1 kali, dan seterusnya sampai $n - 1$ :

0 + 1 + 2 + \dots + (n - 1) = \frac{n (n - 1)}{2} = \frac{1}{2} n^{2} - \frac{1}{2} n

Untuk $n = 16$ , hasilnya $\frac{16 \cdot 15}{2} = 120$ , dan kalau kodenya dijalankan, c memang berakhir di 120. Suku dominannya $n^{2}$ , jadi jawaban: $O (n^{2})$ . Loop segitiga memang kira-kira setengah lebih cepat dari soal 3, tapi kelas pertumbuhannya sama.

#Soal 5 dan 6: dari mana log n muncul?

#Soal 5. Variabel dikali 2

i = 1
while i < n:
    i *= 2
    c += 1

Nilai $i$ berjalan $1, 2, 4, 8, \dots$ dan berhenti begitu $i \geq n$ . Setelah $k$ iterasi, $i = 2^{k}$ . Loop berhenti saat $2^{k} \geq n$ , yaitu $k = ⌈ \log_{2} n ⌉$ . Untuk $n = 1000$ , nilai $i$ yang dilewati adalah 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, total 10 iterasi, dan $⌈ \log_{2} 1000 ⌉ = 10$ . Jawaban: $O (\log n)$ .

Hal yang sama berlaku untuk i //= 2 yang dimulai dari $n$ , dan untuk binary search yang membuang separuh data tiap langkah.

#Soal 6. Luar linear, dalam logaritmik

for i in range(n):
    j = 1
    while j < n:
        j *= 2
        c += 1

Loop dalam tidak bergantung pada $i$ , jadi aturan kali berlaku: $n \cdot ⌈ \log_{2} n ⌉$ . Untuk $n = 16$ , hasilnya $16 \cdot 4 = 64$ . Jawaban: $O (n \log n)$ .

Basis logaritma tidak ditulis di dalam Big O. Alasannya, $\log_{2} n = \frac{\log_{10} n}{\log_{10} 2}$ , dan $\frac{1}{\log_{10} 2}$ hanyalah konstanta.

#Soal 7 dan 8: jebakan yang membuat jawaban meleset

#Soal 7. Loop dalam bergantung pada m

for i in range(n):
    for j in range(m):
        c += 1

Banyak mahasiswa langsung menulis $O (n^{2})$ . Padahal ada dua input yang berbeda, misalnya $n$ baris dan $m$ kolom sebuah matriks. Jawaban yang benar: $O (n \cdot m)$ . Jawaban ini baru boleh disederhanakan menjadi $O (n^{2})$ kalau soal menyatakan $m = n$ .

#Soal 8. Bersarang tapi linear

i = n
while i > 0:
    for j in range(i):
        c += 1
    i //= 2

Ada loop di dalam loop, dan loop luar jalan sekitar $\log_{2} n$ kali, jadi godaannya menjawab $O (n \log n)$ . Hitung saja isinya: loop dalam jalan $n$ kali, lalu $\frac{n}{2}$ , lalu $\frac{n}{4}$ , dan seterusnya.

n + \frac{n}{2} + \frac{n}{4} + \dots + 1 < 2 n

Untuk $n = 16$ , totalnya $16 + 8 + 4 + 2 + 1 = 31$ , di bawah $2 \cdot 16 = 32$ . Jawaban: $O (n)$ . Soal ini menunjukkan kenapa aturan "bersarang dikali" hanya berlaku kalau loop dalam punya panjang tetap.

#Rangkuman jawaban dan seberapa besar bedanya

Soal	Pola	Iterasi tepat	Big O
1	Loop tunggal	$n$	$O (n)$
2	Dua loop berurutan	$2 n$	$O (n)$
3	Bersarang penuh	$n^{2}$	$O (n^{2})$
4	Bersarang segitiga	$\frac{n (n - 1)}{2}$	$O (n^{2})$
5	`i *= 2`	$⌈ \log_{2} n ⌉$	$O (\log n)$
6	Luar $n$ , dalam `j *= 2`	$n ⌈ \log_{2} n ⌉$	$O (n \log n)$
7	Luar $n$ , dalam $m$	$n m$	$O (n m)$
8	Dalam mengecil separuh	$< 2 n$	$O (n)$

Supaya terasa bedanya, ini jumlah langkah untuk tiga ukuran input:

$n$	$\log_{2} n$	$n \log_{2} n$	$n^{2}$
10	3,3	33	100
1.000	10,0	sekitar 10 ribu	1 juta
1.000.000	19,9	sekitar 20 juta	$10^{12}$

Di $n$ sejuta, algoritma $O (n \log n)$ butuh sekitar 20 juta langkah, sedangkan $O (n^{2})$ butuh sejuta juta. Itu alasan sorting di tracing bubble, selection, dan insertion sort terasa lambat untuk data besar dibanding merge sort.

#Kesalahan yang paling sering saat menghitung Big O

Menjumlah padahal harus mengalikan. Soal 3 dijawab $O (2 n)$ karena "ada dua loop". Dua loop bersarang dikalikan.
Mengalikan padahal harus menjumlah. Kebalikannya, soal 2 dijawab $O (n^{2})$ . Lihat indentasinya: kalau loop kedua tidak berada di dalam loop pertama, jumlahkan.
Menyertakan konstanta. $O (2 n)$ , $O (n / 2)$ , dan $O (3 n^{2} + 5)$ bukan jawaban yang salah secara matematis, tapi hampir semua dosen akan mengurangi nilai karena bentuknya belum disederhanakan. Tulis $O (n)$ dan $O (n^{2})$ .
Menyamakan semua loop bersarang dengan $n^{2}$ . Soal 7 dan 8 menunjukkan dua cara loop bersarang tidak menghasilkan $n^{2}$ .
Menghitung satu iterasi sebagai satu langkah padahal isinya memanggil fungsi. Kalau badan loop memanggil sorted(data) atau x in daftar, operasi itu sendiri bukan $O (1)$ . Pencarian in pada list Python adalah $O (n)$ , jadi loop $n$ kali yang berisi in menjadi $O (n^{2})$ .

#Cara membuktikan Big O dengan konstanta C dan n0

Definisi formalnya: $f (n) = O (g (n))$ kalau ada konstanta positif $C$ dan $n_{0}$ sehingga $f (n) \leq C \cdot g (n)$ untuk semua $n \geq n_{0}$ . Soal pembuktian biasanya meminta kamu menemukan pasangan $C$ dan $n_{0}$ itu.

Contoh: buktikan $f (n) = 3 n^{2} + 5 n + 2$ adalah $O (n^{2})$ .

Cara cepat: untuk $n \geq 1$ , berlaku $n \leq n^{2}$ dan $1 \leq n^{2}$ . Ganti setiap suku dengan batas atasnya:

3 n^{2} + 5 n + 2 \leq 3 n^{2} + 5 n^{2} + 2 n^{2} = 10 n^{2}

Jadi $C = 10$ dan $n_{0} = 1$ memenuhi definisi. Selesai.

Pasangan itu tidak unik. Kalau kamu ingin $C$ lebih kecil, misalnya $C = 4$ , syaratnya menjadi $3 n^{2} + 5 n + 2 \leq 4 n^{2}$ , atau $n^{2} - 5 n - 2 \geq 0$ . Akar positifnya $\frac{5 + \sqrt{33}}{2} \approx 5,37$ , jadi $n_{0} = 6$ . Cek: di $n = 6$ , ruas kiri $108 + 30 + 2 = 140$ dan ruas kanan $144$ , benar. Di $n = 5$ , ruas kiri $102$ dan ruas kanan $100$ , gagal. Pembuktian dengan $C = 4, n_{0} = 6$ sama sahnya dengan $C = 10, n_{0} = 1$ .

#Rekurensi T(n) = 2T(n/2) + n sebagai jembatan ke teorema master

Begitu kode memanggil dirinya sendiri, menghitung loop tidak lagi cukup. Merge sort adalah contoh klasik: fungsi membagi data jadi dua, memanggil dirinya untuk tiap separuh, lalu menggabungkan hasilnya dalam $n$ langkah. Waktu jalannya ditulis sebagai rekurensi:

T (n) = 2 T (\frac{n}{2}) + n, T (1) = 1

Cara paling mudah memahaminya adalah pohon rekursi. Gambar berikut untuk $n = 8$ .

Pohon rekursi T(n) = 2T(n/2) + n untuk n = 8: setiap level berbiaya 8, ada tiga level pembagian ditambah level daun, total 32

Setiap level punya biaya total $n$ , karena jumlah simpul berlipat dua sementara ukurannya mengecil separuh. Banyaknya level pembagian adalah $\log_{2} n$ , ditambah satu level daun yang berisi $n$ kasus dasar. Totalnya:

T (n) = n \log_{2} n + n

Cek dengan menghitung manual: $T (2) = 2 \cdot 1 + 2 = 4$ , $T (4) = 2 \cdot 4 + 4 = 12$ , $T (8) = 2 \cdot 12 + 8 = 32$ . Rumus memberi $8 \cdot 3 + 8 = 32$ . Cocok. Jadi $T (n) = O (n \log n)$ .

Teorema master memberi jawaban yang sama tanpa menggambar. Untuk bentuk $T (n) = a T (n / b) + f (n)$ , di sini $a = 2$ , $b = 2$ , dan $n^{\log_{b} a} = n^{1} = n$ . Karena $f (n) = n$ tumbuh sama cepat dengan $n^{\log_{b} a}$ , rekurensi masuk kasus kedua dan hasilnya $Θ (n \log n)$ . Kasus pertama dan ketiga berlaku kalau $f (n)$ jelas lebih lambat atau lebih cepat dari $n^{\log_{b} a}$ . Rekursi yang lebih sederhana, seperti faktorial dan Fibonacci, dibahas langkah demi langkah di rekursi Python dan tracing call stack.

#FAQ

#Apa beda Big O, Big Omega, dan Big Theta?

Big O adalah batas atas, Big Omega batas bawah, dan Big Theta berarti keduanya sekaligus. Soal 3 adalah $Θ (n^{2})$ karena jumlah langkahnya tepat $n^{2}$ . Menulis $O (n^{3})$ untuk soal 3 secara teknis tidak salah, tapi tidak informatif, sehingga di tugas kamu diminta batas yang paling ketat.

#Apakah Big O sama dengan kasus terburuk?

Tidak persis. Big O adalah notasi untuk batas atas sebuah fungsi, sedangkan kasus terburuk, rata-rata, dan terbaik adalah tiga fungsi berbeda. Insertion sort, misalnya, punya kasus terbaik $O (n)$ untuk data yang sudah urut dan kasus terburuk $O (n^{2})$ untuk data terbalik. Kalau soal tidak menyebut, biasanya yang diminta kasus terburuk.

#Kenapa O(1) tetap O(1) walaupun isinya 100 baris?

Karena jumlah langkahnya tidak bergantung pada $n$ . Loop for i in range(100) jalan 100 kali, baik datanya berisi 10 maupun sejuta elemen. Konstanta sebesar apa pun ditulis $O (1)$ .

#Bagaimana menghitung Big O kode dengan if-else?

Ambil cabang yang paling mahal. Kalau cabang if berisi loop $O (n)$ dan cabang else berisi satu perintah $O (1)$ , seluruh blok dihitung $O (n)$ untuk kasus terburuk.

#Apakah O(n log n) selalu lebih cepat dari O(n²)?

Untuk $n$ besar, ya. Untuk $n$ sangat kecil, konstanta yang dibuang Big O bisa membuat algoritma $O (n^{2})$ menang. Itu sebabnya beberapa implementasi sorting di bahasa pemrograman memakai insertion sort untuk potongan data yang pendek.