Analisis · Pelajaran 2 dari 10
Menganalisis perulangan
10 menit baca · BelajarCode
Kompleksitas algoritma iteratif biasanya dihitung dari banyaknya eksekusi operasi dasar di dalam perulangan.
Pola-pola dasar
| Pola | Banyak iterasi | Kompleksitas |
|---|---|---|
for i in range(n) | n | Θ(n) |
| Dua perulangan bersarang masing-masing n | n² | Θ(n²) |
for i in range(n) lalu for j in range(i) | 0 + 1 + ... + (n - 1) = n(n - 1)/2 | Θ(n²) |
i = 1, ulangi selama i < n dengan i *= 2 | sekitar log₂ n | Θ(log n) |
| Perulangan Θ(n) di dalam perulangan Θ(log n) | n log n | Θ(n log n) |
Memeriksa dengan menghitung langkah
1def hitung(n):2 a = sum(1 for i in range(n) for j in range(n))3 b = sum(1 for i in range(n) for j in range(i))4 c = 05 i = 16 while i < n:7 c += 18 i *= 29 d = 010 i = 111 while i < n:12 for j in range(n):13 d += 114 i *= 215 return a, b, c, d1617for n in [16, 64, 256]:18 a, b, c, d = hitung(n)19 print(f"n={n:>3}: bersarang={a:>6} segitiga={b:>6} logaritmik={c:>2} n log n={d:>5}")n= 16: bersarang= 256 segitiga= 120 logaritmik= 4 n log n= 64 n= 64: bersarang= 4096 segitiga= 2016 logaritmik= 6 n log n= 384 n=256: bersarang= 65536 segitiga= 32640 logaritmik= 8 n log n= 2048
Perulangan segitiga melakukan kira-kira separuh pekerjaan perulangan bersarang penuh, tetapi tetap Θ(n²): konstanta 1/2 tidak mengubah kelas pertumbuhannya.
Perulangan yang menipu
Tidak semua perulangan bersarang berarti Θ(n²). Perhatikan dua penunjuk yang hanya bergerak maju:
1def pasangan_berjumlah(data, target):2 kiri, kanan = 0, len(data) - 13 langkah = 04 while kiri < kanan:5 langkah += 16 s = data[kiri] + data[kanan]7 if s == target:8 return (data[kiri], data[kanan]), langkah9 if s < target:10 kiri += 111 else:12 kanan -= 113 return None, langkah1415data = list(range(0, 2000, 2))16print(pasangan_berjumlah(data, 1998 + 1996))17print(pasangan_berjumlah(data, 7))((1996, 1998), 999) (None, 999)
Pada data terurut, setiap langkah memajukan kiri atau memundurkan kanan, sehingga total langkah paling banyak n - 1. Algoritma ini Θ(n), bukan Θ(n²). Analisis yang baik melihat berapa kali pekerjaan sungguh dilakukan, bukan sekadar menghitung tingkat perulangan.
Cek pemahaman
Berapa kompleksitas potongan kode i = n lalu while i > 1: i = i // 3?
Latihan
Analisis potongan kode
Tentukan kompleksitas fungsi berikut, lalu periksa dengan menghitung jumlah eksekusi baris total += 1 untuk beberapa n.
1def misteri(n):2 total = 03 for i in range(1, n + 1):4 j = 15 while j <= i:6 total += 17 j *= 28 return totalPembahasan
Untuk setiap i, perulangan dalam berjalan sekitar log₂ i + 1 kali. Totalnya Σ log i untuk i = 1 sampai n, yaitu log(n!) yang setara dengan Θ(n log n).
1import math23def misteri(n):4 total = 05 for i in range(1, n + 1):6 j = 17 while j <= i:8 total += 19 j *= 210 return total1112for n in [100, 1000, 10000]:13 print(n, misteri(n), round(misteri(n) / (n * math.log2(n)), 3))100 580 0.873 1000 8987 0.902 10000 123631 0.93
Rasio terhadap n log n mendekati konstanta (perlahan menuju 1), sesuai dengan Θ(n log n).
Jalankan contoh kode di pelajaran ini tanpa instalasi lewat compiler Python online.