Skip to content

Membandingkan kompleksitas waktu Padovan Sequence secara Rekursif dan Dynamic Programming (DP)

Notifications You must be signed in to change notification settings

Otniel113/PadovanSequence_DP

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

6 Commits
 
 
 
 

Repository files navigation

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)

PadovanGambar

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

PadovanRumus

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
Rekursif

Dynamic Programming Memoization
Memoization

Dynamic Programming Tabulation
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
Padovan_Grafik_70

About

Membandingkan kompleksitas waktu Padovan Sequence secara Rekursif dan Dynamic Programming (DP)

Topics

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages