Analisis kode

Menaksir kompleksitas dari kode berarti membaca struktur perulangannya, menjalankan sedikit aritmetika, lalu menutupnya dengan notasi Big-O. Topik ini melatih keterampilan tersebut pada pola yang paling sering muncul, yaitu kode berurutan, perulangan tunggal, perulangan bersarang, dan perulangan yang batasnya menggandakan diri. Setiap pola dianalisis langkah demi langkah sampai rumusnya, dan seluruh taksiran dibuktikan dengan penghitung operasi di bagian akhir.

Kaedah penjumlahan untuk kode berurutan#

Kaedah pertama berlaku untuk blok yang dijalankan satu demi satu, yaitu jumlahkan operasinya lalu pertahankan suku yang tumbuh paling cepat. Dua perulangan tunggal yang ditulis berurutan mengerjakan $n$ langkah lalu $n$ langkah lagi. Totalnya $n + n = 2n$, dan konstanta 2 dibuang sehingga hasilnya $O(n)$. Urutan penulisan blok tidak mengubah hasil akhirnya, karena penjumlahan tidak memedulikan urutan sukunya.

n = 1000
langkah = 0
for i in range(n):       # blok pertama: n langkah
    langkah += 1
for j in range(n):       # blok kedua: n langkah lagi
    langkah += 1
print(langkah)

2000

Penghitung mencetak 2000 untuk $n = 1000$, sesuai taksiran $2n$. Ketika salah satu blok jauh lebih berat, blok yang lain praktis tak terlihat. Satu perulangan tunggal di depan sepasang perulangan bersarang menyumbang $n + n^2$ langkah, suku $n^2$ yang menang, sehingga keseluruhannya tetap $O(n^2)$. Kaedah penjumlahan selalu berakhir pada suku dominannya.

Kaedah ini bekerja untuk berbagai bentuk blok, bukan hanya perulangan yang tampak jelas. Memanggil fungsi berbiaya $O(\log n)$ sekali lalu menyusuri daftar $n$ elemen menyumbang $O(\log n) + O(n)$ yang berakhir di $O(n)$. Membaca berkas berbiaya $O(n)$ lalu mengurutkan isinya berbiaya $O(n \log n)$ berakhir di $O(n \log n)$. Suku dengan kurva paling curam selalu mewakili seluruh deret blok yang dijalankan berurutan.

Kaedah perkalian untuk perulangan bersarang#

Kaedah kedua berlaku ketika perulangan berada di dalam perulangan lain, yaitu kalikan banyaknya langkah keduanya. Perulangan luar mengerjakan $n$ putaran, dan setiap putaran membiarkan perulangan dalam mengerjakan $n$ putaran penuh. Totalnya $n \times n = n^2$, sehingga strukturnya berada di kelas $O(n^2)$.

n = 1000
langkah = 0
for i in range(n):       # setiap putaran luar
    for j in range(n):   # membiarkan n putaran dalam
        langkah += 1
print(langkah)

1000000

Batas dalam yang menyusut juga termasuk pola ini. Perulangan dalam yang hanya mengerjakan $i$ putaran pada putaran ke-$i$ dari luar menghasilkan jumlah segitiga berikut.

n = 1000
langkah = 0
for i in range(n):       # putaran ke-i
    for j in range(i):   # hanya berjalan i kali
        langkah += 1
print(langkah)

499500

Untuk $n = 1000$, rumus segitiga memberi 499.500, sama persis dengan penghitung. Pembagi dua adalah konstanta, sehingga kelasnya tetap $O(n^2)$ meskipun jumlah langkah aslinya separuh dari pola persegi. Dua fragmen di atas terlihat berbeda di layar, tetapi keduanya berdiri di kelas yang sama.

Perkalian juga berlaku ketika yang dikalikan bukan perulangan, melainkan biaya satu langkah. Perulangan tunggal yang di dalamnya memanggil pencarian biner mengerjakan $n$ putaran berbiaya $\log n$, sehingga totalnya $O(n \log n)$. Pola ini mudah terlewat karena biaya baris dalam tersembunyi di balik pemanggilan fungsi. Karena itu biaya setiap fungsi yang dipanggil perlu diketahui lebih dahulu sebelum kode pemanggilnya dianalisis.

Batas yang menggandakan diri#

Pola ketiga menyembunyikan $O(\log n)$ di balik bentuk yang tidak tampak seperti perulangan biasa. Ketika batas perulangan menggandakan nilai variabelnya, jumlah langkahnya sama dengan berapa kali variabel itu harus digandakan agar melewati $n$. Rumusnya $2^k \ge n$ dengan $k$ banyaknya langkah, sehingga $k = \lceil \log_2 n \rceil$.

n = 1000000
i = 1
langkah = 0
while i < n:             # batas naik dua kali lipat setiap putaran
    i *= 2
    langkah += 1
print(langkah, i)

20 1048576

Penghitung melaporkan 20 langkah untuk $n = 1000000$, dan nilai i berhenti di 1048576, yaitu $2^{20}$. Pola inilah yang menggerakkan pencarian biner, yang membuang separuh kandidat pada setiap perbandingan sehingga sejuta kandidat habis dalam dua puluh langkah. Kapan pun sebuah variabel digandakan atau dibelah dua di setiap putaran, dugaan pertama yang wajar adalah $O(\log n)$.

Arahnya bebas bolak-balik. Variabel yang membelah diri, misalnya i //= 2 pada perulangan yang berhenti saat nilainya mencapai satu, menempuh jumlah langkah yang sama dengan variabel yang menggandakan diri. Yang menentukan bukan operasi gandakan atau belah, melainkan bahwa ruang kerjanya berlipat atau menyusut dengan faktor tetap di setiap putaran. Setiap faktor tetap yang lebih dari satu menghasilkan $O(\log n)$, dengan pangkal berapa pun.

Membuktikan taksiran dengan penghitung#

Seluruh kaedah di atas menghasilkan taksiran, dan taksiran layak diuji. Uji yang paling ringkas adalah doubling test, yaitu menjalankan algoritma yang sama pada $n$ yang berlipat dua lalu membandingkan jumlah langkahnya. Bila langkahnya berlipat empat, bentuk kurvanya kuadrat, karena masukan berlipat dua dan $2^2 = 4$. Berkas berikut menerapkannya pada algoritma pencarian pasangan angka yang memeriksa setiap pasangan. Target yang dipakai adalah angka yang tidak pernah ada di daftar, sehingga fungsi selalu terseret ke kasus terburuknya dan menyusuri seluruh pasangan.

# Taksiran O(n^2) dibandingkan dengan penghitung operasi sesungguhnya.
# Fungsi memeriksa setiap pasangan angka, mencari dua nilai yang
# berjumlah sama dengan target.

def cari_pasangan(angka, target):
    langkah = 0
    n = len(angka)
    for i in range(n):
        for j in range(i + 1, n):
            langkah += 1
            if angka[i] + angka[j] == target:
                return langkah, (i, j)
    return langkah, None

data = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7, 9, 3, 2, 3, 8, 4, 6, 2, 6, 4, 3, 3, 8, 3, 2, 7, 9, 5]
print(f"{'n':>5} {'langkah':>8} {'n*(n-1)/2':>10} {'rasio':>6}")
sebelumnya = None
for ukuran in (8, 16, 32):
    langkah, hasil = cari_pasangan(data[:ukuran], 100)
    taksiran = ukuran * (ukuran - 1) // 2
    rasio = f"{langkah / sebelumnya:.1f}x" if sebelumnya else "-"
    print(f"{ukuran:>5} {langkah:>8} {taksiran:>10} {rasio:>6}")
    sebelumnya = langkah

    n  langkah  n*(n-1)/2  rasio
    8       28         28      -
   16      120        120   4.3x
   32      496        496   4.1x

Tiga baris tabelnya mengikuti rumus $\frac{n(n-1)}{2}$ dengan tepat, dan rasio antar barisnya menghampiri empat setiap $n$ berlipat dua. Rasio 4,3 dan 4,1 belum persis empat karena suku $(n-1)$ pada rumus itu masih terasa pada $n$ kecil, dan angka empat baru tepat ketika $n$ jauh lebih besar. Meski begitu, bukti empirisnya sudah cukup untuk menempatkan fungsi tersebut di kelas $O(n^2)$, tanpa perlu membaca prosesor maupun jam. Bila nanti bertemu fungsi yang kelasnya tidak pasti, pengujian penggandaan seperti ini adalah langkah pertama yang murah untuk dilakukan.

Ringkasan#

• Kode berurutan dijumlahkan lalu diringkas ke suku dominannya, sehingga $n + n^2$ tetap $O(n^2)$.
• Perulangan bersarang dikalikan, baik bentuk penuh $n \times n = n^2$ maupun bentuk segitiga $\frac{n(n-1)}{2}$ yang kelasnya tetap sama.
• Batas yang menggandakan diri menghasilkan $O(\log n)$, karena rumusnya $2^k \ge n$.
• Pengujian penggandaan membuktikan taksiran secara empiris, dengan rasio langkah empat untuk kurva kuadrat ketika $n$ berlipat dua.

Referensi#

• Algorithms, 4th ed. — Princeton University — Situs buku teks yang membahas pengujian penggandaan (doubling test) dan analisis empiris algoritma.
• Analysis of algorithms — Wikipedia — Ringkasan kaedah penjumlahan dan perkalian pada analisis perulangan.