Kompleksitas waktu & notasi asimtotik

Menghitung T(n), notasi Big-O, Big-Omega, Big-Theta, aturan praktis, dan menyelesaikan rekurensi dengan Teorema Master.

Dua algoritma bisa sama-sama benar tapi berbeda jauh kecepatannya. Analisis kompleksitas mengukur bagaimana jumlah langkah (atau memori) bertumbuh ketika ukuran input $n$ membesar, terlepas dari komputer atau bahasa yang dipakai.

Menghitung T(n)

Hitung operasi dasar (perbandingan, assignment, operasi aritmatika) sebagai fungsi dari $n$ :

function jumlahPasangan(a: number[]) {
  let total = 0;                       // 1
  for (let i = 0; i < a.length; i++)       // n kali
    for (let j = i + 1; j < a.length; j++) //   n-1-i kali
      total += a[i] * a[j];            // dieksekusi n(n-1)/2 kali
  return total;
}

$T(n) = \frac{n(n-1)}{2} + c$ . Untuk $n$ besar, suku $n^2$ yang mendominasi, sehingga kita tulis $T(n) = O(n^2)$ .

Notasi asimtotik

Big-O $O(g)$ : batas atas. $f(n) = O(g(n))$ jika ada konstanta $c > 0$ dan $n_0$ sehingga $f(n) \le c \cdot g(n)$ untuk semua $n \ge n_0$ .
Big-Omega $\Omega(g)$ : batas bawah, $f(n) \ge c \cdot g(n)$ .
Big-Theta $\Theta(g)$ : batas ketat, $f$ ada di $O(g)$ dan $\Omega(g)$ sekaligus.

n = 20

kompleksitas	n = 10	n = 100	n = 1.000	n = 1.000.000
O(1)	1	1	1	1
O(log n)	3	7	10	20
O(n)	10	100	1.000	1.000.000
O(n log n)	33	664	9.966	19.931.569
O(n²)	100	10.000	1.000.000	1.000.000.000.000
O(2ⁿ)	1.024	≈ ∞	≈ ∞	≈ ∞

Dengan 10⁸ operasi/detik: n = 10⁶ dengan O(n²) butuh ~3 jam, sementara O(n log n) selesai dalam 0,2 detik.

Aturan praktis

Abaikan konstanta: $O(5n) = O(n)$ .
Ambil suku dominan: $O(n^2 + n \log n) = O(n^2)$ .
Loop berurutan dijumlah, loop bersarang dikali.
Loop yang variabelnya dikali/dibagi konstanta setiap iterasi (misalnya i *= 2) berjalan $O(\log n)$ kali.

Rekurensi & Teorema Master

Algoritma divide and conquer menghasilkan rekurensi berbentuk

T(n) = a\,T\!\left(\frac{n}{b}\right) + f(n)

dengan $a$ = banyak submasalah, $n/b$ = ukuran tiap submasalah, $f(n)$ = biaya membagi + menggabung. Bandingkan $f(n)$ dengan $n^{\log_b a}$ :

Kasus	Syarat	Hasil
1	$f(n) = O(n^{\log_b a - \epsilon})$	$T(n) = \Theta(n^{\log_b a})$
2	$f(n) = \Theta(n^{\log_b a})$	$T(n) = \Theta(n^{\log_b a} \log n)$
3	$f(n) = \Omega(n^{\log_b a + \epsilon})$ (+ syarat regularitas)	$T(n) = \Theta(f(n))$

Contoh:

Merge sort: $T(n) = 2T(n/2) + n$ . Di sini $n^{\log_2 2} = n = f(n)$ , kasus 2, sehingga $\Theta(n \log n)$ .
Binary search: $T(n) = T(n/2) + 1$ . Di sini $n^{\log_2 1} = 1 = f(n)$ , kasus 2, sehingga $\Theta(\log n)$ .
Karatsuba: $T(n) = 3T(n/2) + n$ . Di sini $n^{\log_2 3} \approx n^{1{,}585}$ lebih besar dari $f(n)$ , kasus 1, sehingga $\Theta(n^{1{,}585})$ .