Analisis · Pelajaran 1 dari 10

Notasi asimtotik

10 menit baca · BelajarCode

Saat menganalisis algoritma, kita tertarik pada laju pertumbuhan waktu jalannya ketika ukuran masukan n membesar, bukan pada detik di komputer tertentu. Notasi asimtotik memberi bahasa yang tepat untuk itu.

Definisi

Tiga notasi asimtotik

Notasi	Dibaca	Definisi	Makna
f(n) = O(g(n))	Big-O	Ada c > 0 dan n₀ sehingga f(n) ≤ c·g(n) untuk semua n ≥ n₀	g adalah batas atas pertumbuhan f
f(n) = Ω(g(n))	Big-Omega	Ada c > 0 dan n₀ sehingga f(n) ≥ c·g(n) untuk semua n ≥ n₀	g adalah batas bawah pertumbuhan f
f(n) = Θ(g(n))	Big-Theta	f(n) = O(g(n)) dan f(n) = Ω(g(n))	f tumbuh setara dengan g

Contoh pembuktian. Tunjukkan bahwa f(n) = 3n² + 5n + 2 adalah O(n²).

Untuk n ≥ 1 berlaku 5n ≤ 5n² dan 2 ≤ 2n². Jadi f(n) ≤ 3n² + 5n² + 2n² = 10n². Pilih c = 10 dan n₀ = 1, maka f(n) ≤ c·n² untuk semua n ≥ n₀. Karena juga f(n) ≥ 3n² untuk n ≥ 1, f(n) = Θ(n²).

Inilah alasan konstanta dan suku berorde lebih rendah diabaikan: untuk n besar, suku dengan pertumbuhan tertinggi mendominasi.

Membandingkan pertumbuhan

Python

1import math23fungsi = [4    ("log n", lambda n: math.log2(n)),5    ("n", lambda n: n),6    ("n log n", lambda n: n * math.log2(n)),7    ("n^2", lambda n: n ** 2),8    ("2^n", lambda n: 2 ** n),9]10def tulis(x):11    return f"{x:>12.0f}" if x < 1e9 else f"{x:>12.2e}"1213print(f"{'n':>4}" + "".join(f"{nama:>12}" for nama, _ in fungsi))14for n in [8, 16, 32, 64]:15    print(f"{n:>4}" + "".join(tulis(f(n)) for _, f in fungsi))

Keluaran

   n       log n           n     n log n         n^2         2^n
   8           3           8          24          64         256
  16           4          16          64         256       65536
  32           5          32         160        1024    4.29e+09
  64           6          64         384        4096    1.84e+19

Angka seperti 1.84e+19 artinya 1,84 dikali 10 pangkat 19. Fungsi eksponensial meledak jauh lebih cepat dari semua fungsi polinomial. Algoritma O(2ⁿ) praktis tidak bisa dipakai untuk n di atas beberapa puluh.

Urutan kelas pertumbuhan

O(1) < O(log n) < O(√n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2ⁿ) < O(n!)

Big-O bukan berarti kasus terburuk

Big-O, Omega, dan Theta adalah notasi tentang fungsi, bukan tentang kasus terbaik atau terburuk. Kita bisa berkata "waktu terburuk insertion sort adalah Θ(n²)" dan "waktu terbaiknya Θ(n)". Dalam percakapan sehari-hari, orang sering memakai Big-O untuk kasus terburuk, tetapi kedua konsep itu berbeda.

Cek pemahaman

Manakah pernyataan yang benar?

n log n = O(n²)2ⁿ = O(n³)100n = O(log n)n² = O(n log n)

Latihan

Buktikan batasnya

Tunjukkan bahwa f(n) = 2n³ - 10n² + 7 adalah Θ(n³) dengan mencari konstanta yang memenuhi definisi, lalu periksa secara numerik bahwa f(n) / n³ mendekati sebuah konstanta.

Pembahasan

Batas atas. Untuk n ≥ 1: f(n) ≤ 2n³ + 7 ≤ 2n³ + 7n³ = 9n³. Pilih c = 9, n₀ = 1.

Batas bawah. Untuk n ≥ 10: 10n² ≤ n³, sehingga f(n) ≥ 2n³ - n³ + 7 ≥ n³. Pilih c = 1, n₀ = 10.

Karena ada batas atas dan batas bawah berorde n³, f(n) = Θ(n³).