Relasi Rekurensi

Topik ini membahas relasi rekurensi, yaitu aturan yang menentukan setiap suku dari suku-suku sebelumnya, beserta dua cara penyelesaiannya, mulai dari persamaan karakteristik hingga pembukaan relasi menjadi deret. Kaitannya dengan analisis algoritma ditunjukkan pada relasi pembagian masalah yang menghasilkan kompleksitas $O(n \log n)$. Setiap bentuk penyelesaian diverifikasi secara numerik dengan NumPy, sehingga kecocokan bentuk tertutup dengan perhitungan suku demi suku dapat diperiksa ulang langsung dari kode.

Relasi rekurensi sebagai definisi berantai#

Relasi rekurensi (recurrence relation) mendefinisikan suku ke-$n$ dari satu atau beberapa suku sebelumnya, dan hanya berhenti apabila kasus dasarnya ditetapkan. Definisi berantai ini lazim dalam matematika diskrit, misalnya faktorial $n! = n \times (n-1)!$ dengan kasus dasar $0! = 1$. Contoh yang paling sering ditemui adalah deret Fibonacci, yang setiap sukunya dijumlahkan dari dua sukunya sebelumnya,

Program berikut mengisi seluruh suku dari relasi tersebut menggunakan perulangan biasa, mulai dari kasus dasar hingga suku kesepuluh. Tabel NumPy digunakan sebagai wadahnya sehingga setiap suku yang sudah terisi dapat dibaca kembali pada perhitungan suku berikutnya.

import numpy as np

# relasi rekurensi Fibonacci dengan kasus dasar F(0) = 0 dan F(1) = 1
F = np.zeros(11, dtype=np.int64)
F[1] = 1
for n in range(2, 11):
    F[n] = F[n - 1] + F[n - 2]

print("F(n) untuk n = 0 sampai 10")
print(F)

F(n) untuk n = 0 sampai 10
[ 0  1  1  2  3  5  8 13 21 34 55]

Setiap suku diisi satu kali dengan menjumlahkan dua nilai yang sudah tersimpan, sehingga biaya perhitungannya berbanding lurus dengan banyaknya suku. Pendekatan ini sekaligus menjadi pola pemrograman dinamis (dynamic programming), yaitu menyimpan hasil relasi rekurensi agar tidak dihitung berulang. Rumus yang menutup perulangan tersebut tanpa suku sebelumnya dinamakan bentuk tertutup, dan pembangunannya dijelaskan pada bagian berikut.

Persamaan karakteristik dan bentuk tertutup#

Relasi linear homogen dengan koefisien tetap dapat diselesaikan dengan menebak solusi berbentuk $r^n$, lalu menuntaskan nilai $r$ yang membuat tebakan itu sah. Bentuk ini dipilih karena relasi semacam itu memang tumbuh secara geometris. Mensubstitusikan $F(n) = r^n$ ke dalam relasi Fibonacci dan membaginya dengan $r^{n-2}$ menghasilkan persamaan karakteristik (characteristic equation),

Kedua akarnya adalah $\phi = \frac{1 + \sqrt{5}}{2} \approx 1.618034$, yang dikenal sebagai rasio emas (golden ratio), dan $\psi = \frac{1 - \sqrt{5}}{2} \approx -0.618034$. Suku $\psi^n$ menyusut mendekati nol karena $|\psi| < 1$, sehingga pengaruhnya pada suku yang besar dapat diabaikan. Solusi umumnya merupakan gabungan kedua akar, dan kasus dasar $F(0) = 0$, $F(1) = 1$ menetapkan koefisiennya sehingga diperoleh rumus Binet,

Program berikut mencari kedua akar menggunakan np.roots, lalu membandingkan rumus Binet dengan pengisian relasi suku demi suku pada $n$ sampai $14$. Masukan np.roots berupa koefisien polinomial mulai dari pangkat tertinggi, yaitu [1.0, -1.0, -1.0] untuk $r^2 - r - 1$.

import numpy as np

# persamaan karakteristik r^2 - r - 1 = 0 dari relasi F(n) = F(n-1) + F(n-2)
akar = np.roots([1.0, -1.0, -1.0])
phi = akar[0]
psi = akar[1]
print(f"akar persamaan karakteristik: {akar}")
print(f"phi = {phi:.6f}, psi = {psi:.6f}")

def fibonacci_tutup(n):
    # rumus Binet dari kedua akar karakteristik
    return (phi**n - psi**n) / (phi - psi)

def fibonacci_iterasi(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

deviasi = max(abs(fibonacci_tutup(n) - fibonacci_iterasi(n)) for n in range(0, 15))
print(f"deviasi terbesar rumus Binet untuk n = 0 sampai 14: {deviasi:.2e}")

akar persamaan karakteristik: [ 1.61803399 -0.61803399]
phi = 1.618034, psi = -0.618034
deviasi terbesar rumus Binet untuk n = 0 sampai 14: 1.71e-13

Rumus Binet mengembalikan seluruh suku Fibonacci dengan simpangan terbesar sekitar $10^{-13}$, yaitu tingkat pembulatan floating point biasa dan bukan kesalahan rumus. Perbandingan ini memperlihatkan kegunaan persamaan karakteristik, yaitu menyusutkan relasi yang berantai menjadi rumus satu baris. Metode yang sama menutup relasi berorde tiga atau lebih, dengan persamaan karakteristik berderajat sesuai banyaknya suku sebelumnya yang dirujuk.

Membuka relasi menjadi deret#

Cara penyelesaian kedua tidak memerlukan tebakan sama sekali, melainkan membuka (unroll) relasi tersebut beberapa langkah hingga pola penjumlahannya terlihat. Setiap langkah pembukaan mengganti suku $T$ terkecil dengan relasinya, sehingga sisa yang belum selesai terus menyusut. Pada relasi $T(n) = T(n-1) + n$, pembukaan itu berlangsung sebagai berikut,

Relasi berubah menjadi deret bilangan asli, dan deret itu memiliki bentuk tertutup yang telah lama diketahui, yaitu $1 + 2 + \cdots + n = n(n+1)/2$. Kesetaraan ini sekaligus menjadi jembatan menuju analisis algoritma, karena banyak biaya komputasi muncul dalam bentuk penjumlahan berurutan. Program berikut membandingkan kedua bentuknya pada $n = 10$, sekali dengan penjumlahan langsung dan sekali dengan rumusnya.

# relasi T(n) = T(n-1) + n yang dibuka menjadi deret 1 + 2 + ... + n
n = 10
dibuka = sum(range(1, n + 1))
tutup = n * (n + 1) // 2

print(f"{'penjumlahan langsung': <22}: {dibuka}")
print(f"{'rumus n(n + 1) / 2': <22}: {tutup}")

penjumlahan langsung  : 55
rumus n(n + 1) / 2    : 55

Kedua sisi bernilai $55$, sehingga relasi yang dinyatakan berantai terbukti sama dengan rumus perkaliannya. Pembukaan ini juga menunjukkan perubahan biaya dari sudut yang berbeda, yaitu relasi yang dijumlahkan tiap langkah tumbuh seperti kuadrat, bukan seperti garis lurus. Demo berikut membentangkan penjumlahan yang sama secara visual, yaitu satu batang untuk setiap suku $n, n-1, \ldots, 1$ beserta garis pembanding $n^2/2$, sehingga pertumbuhan kuadratnya terlihat langsung ketika penggeser nilai $n$ digerakkan. Pola kerja yang sama diterapkan pada relasi pembagian masalah pada bagian berikut, dengan deret yang sukunya konstan dari tingkat ke tingkat.

Relasi pembagian masalah dan n log n#

Algoritma yang memecah masalah menjadi dua bagian sama besar, mengerjakan keduanya, lalu menggabungkan hasilnya dalam waktu sebanding dengan $n$, membentuk relasi berikut,

Setiap pemanggilan membayar biaya $n$ untuk penggabungan, dan pohon panggilannya menggandakan banyak simpul pada setiap tingkatnya. Susunan seperti ini digunakan oleh banyak algoritma pengurutan dan pembagian masalah lainnya. Gambar berikut memperlihatkan tiga tingkat pertama pohon tersebut beserta biaya setiap tingkatnya.

Banyaknya simpul menggandakan diri setiap tingkat, tetapi biaya per simpul terbagi dua dengan faktor yang sama, sehingga total biaya per tingkat selalu $n$. Tingkatnya habis ketika $n$ telah terbagi sampai satu, yaitu setelah $\log_2 n$ tingkat, sehingga biaya totalnya $n \log_2 n$. Program berikut menilai relasi itu langsung pada pangkat dua, dengan rasio terhadap $n \log_2 n$ sebagai ukurannya.

import math

def T(n):
    # relasi pembagian masalah: T(n) = 2T(n/2) + n dengan kasus dasar T(1) = 1
    if n == 1:
        return 1
    return 2 * T(n // 2) + n

for n in (8, 64, 512, 4096):
    nilai = T(n)
    acuan = n * math.log2(n)
    print(f"n = {n:5d} : T(n) = {nilai:6d}, n log2 n = {acuan:9.1f}, rasio = {nilai / acuan:.4f}")

n =     8 : T(n) =     32, n log2 n =      24.0, rasio = 1.3333
n =    64 : T(n) =    448, n log2 n =     384.0, rasio = 1.1667
n =   512 : T(n) =   5120, n log2 n =    4608.0, rasio = 1.1111
n =  4096 : T(n) =  53248, n log2 n =   49152.0, rasio = 1.0833

Rasio menurun menuju satu seiring $n$ membesar, sesuai perhitungan eksak $T(n) = n \log_2 n + n$ untuk pangkat dua, yang suku $n$-nya makin tak berarti dibandingkan $n \log_2 n$. Notasi $O(n \log n)$ merangkum perilaku itu dengan membuang suku yang tumbuh paling lambat. Alat umum untuk menilai relasi bentuk $T(n) = a\,T(n/b) + f(n)$ dinamakan teorema master (master theorem), dan relasi pada bagian ini termasuk kasus yang paling sering digunakan.

Di mana hal ini ditemui dalam kode#

Analisis merge sort berjalan persis melalui relasi pada bagian sebelumnya, yaitu membagi larik menjadi dua, mengurutkan keduanya, lalu menggabungkannya dalam waktu sebanding dengan panjang lariknya. Relasi $T(n) = 2T(n/2) + O(n)$ yang tumbuh seperti $n \log n$ menjadi alasan kompleksitas algoritma itu ditulis $O(n \log n)$ pada dokumentasi dan buku teks. Penelusuran biner (binary search) memberikan kontras yang ringkas, karena relasinya $T(n) = T(n/2) + O(1)$ dan pembukaannya menghasilkan satu tingkat per pembagian, sehingga biayanya $O(\log n)$.

Relasi rekurensi juga merupakan bentuk tertulis dari perencanaan pemrograman dinamis, yaitu menetapkan kasus dasar, relasi antarsukunya, lalu mengisi tabel sesuai urutan ketergantungan. Deret Fibonacci pada bagian pembuka merupakan contoh paling sederhana dari pola tersebut. Dengan demikian, relasi rekurensi berperan ganda dalam kode sehari-hari, yaitu menaksir biaya algoritma sebelum dijalankan dan menyusun solusi untuk masalah yang suku-sukunya memang saling bergantung.

Ringkasan#

• Relasi rekurensi menentukan setiap suku dari suku-suku sebelumnya dan memerlukan kasus dasar agar berhenti, sebagaimana $F(n) = F(n-1) + F(n-2)$ pada deret Fibonacci.
• Persamaan karakteristik mengubah relasi linear homogen menjadi bentuk tertutup, dan relasi Fibonacci menghasilkan akar $\phi \approx 1.618$ beserta rumus Binet yang terverifikasi numerik.
• Pembukaan relasi $T(n) = T(n-1) + n$ menghasilkan deret $1 + 2 + \cdots + n = n(n+1)/2$.
• Relasi pembagian masalah $T(n) = 2T(n/2) + n$ membayar $n$ per tingkat selama $\log_2 n$ tingkat, sehingga tumbuh seperti $n \log_2 n$ dan menjadi dasar kompleksitas merge sort.

Referensi#

• 6.006 Introduction to Algorithms, Spring 2020 — MIT OpenCourseWare — Materi kuliah algoritma yang menganalisis merge sort melalui relasi rekurensinya.
• numpy.roots — NumPy — Dokumentasi pencarian akar polinomial dari koefisiennya.
• Asymptotic notation — Khan Academy — Artikel notasi kompleksitas yang digunakan untuk menyatakan hasil analisis relasi rekurensi.