PadovanSequence_DP

Membandingkan kompleksitas waktu Padovan Sequence secara:

1. Rekursif
2. Dynamic Programming (Memoization) atau dengan pendakatan Top-Down
3. Dynamic Programming (Tabulation) atau dengan pendekatan Bottom-Up

Penjelasan Padovan Sequence (Barisan Padovan)

Padovan Sequence (Barisan Padovan) adalah barisan yang merupakan relasi rekurensi dengan rumus sebagai berikut:

Sehingga menghasilkan baris seperti : 1,1,1,2,2,3,4,5,7,9,12,...

Agak mirip dengan barisan Fibonacci (Fibonacci Sequence) yang membedakan adalah relasi rekurensinya dan juga basisnya

Kompleksitas

1. Rekursif : O(1.32471^n)
2. DP Memoization (Top-Down) : O(n)
3. DP Tabulation (Bottom-Up) : O(n)

Algoritma

Rekursif

def padovan_biasa(n):
    if (n <= 2):
        return 1
    else:
        return padovan_biasa(n-3) + padovan_biasa(n-2)

Dynamic Programming Memozation

def inisiasiMemori(memori, n):
    for i in range(0,n):
        if (0 <= i <= 2):
            memori.append(1)
        else:
            memori.append(0)
            
def padovan_memoization(memori, n):
    if (memori[n] != 0):
        return memori[n]
    else:
        memori[n] = padovan_memoization(memori, n-3) + padovan_memoization(memori, n-2)
        return memori[n]

Dynamic Programming Tabulation

def padovan_tabulation(n):
    memori_lokal = []
    for i in range(0,n+1):
        if (0 <= i <= 2):
            memori_lokal.append(1)
        else:
            memori_lokal.append(memori_lokal[i-3] + memori_lokal[i-2])
    return memori_lokal[n]

Langkah per Langkah

Rekursif

Dynamic Programming Memoization

Dynamic Programming Tabulation

Hasil Pengamatan

Nilai N adalah inputan user untuk mencari nilai Pandovan ke-n. Tabel berikut berisi waktu eksekusi dalam detik

Nilai n	30	40	50	60	70	1000	2500
Rekursif	0.01	0.03	0.34	5.24	89.59
DP Memozation (Top-Down)	0	0	0	0	0	0.001	0.005
DP Tabulation (Bottom-Up)	0	0	0	0	0	0.001	0.001

Atau dapat dilihat dalam grafik berikut