1. Contoh kasus bilangan fibonacci
function Fibonacci (input n : integer) → integer;
Algoritma :
if (n=0) then
Fibonacci ← 0
else
if (n = 1) then
Fibonacci ← 1
else
Fibonacci ← Fibonacci (n-1) + Fibonacci (n-2)
endif
endif
endfunction
Operasi dasar utama : +
Rekurens : Fibonacci (n-1) + Fibonacci (n-2)
misal : T(2) = Fibonacci(2-1) + Fibonacci(2-2)
= Fibonacci(1)
T(2) = 1
Penghenti : T(1) = 0
Permisalan :
T(n-1) = T(n-1) + T(n-2) + 1 T(n-i) → T(1)
T(n-2) = T(n-2) + T(n-3) + 1 n-i = 1
misal : T(2) = Fibonacci(2-1) + Fibonacci(2-2)
= Fibonacci(1)
T(2) = 1
Penghenti : T(1) = 0
Permisalan :
T(n-1) = T(n-1) + T(n-2) + 1 T(n-i) → T(1)
T(n-2) = T(n-2) + T(n-3) + 1 n-i = 1
T(n-3) = T(n-3) + T(n-4) + 1 -i = 1-n
i = n-1
Sehingga ,
T(n) = T(n-1) + T(n-2) + 1
= T(n-2) + T(n-3) + 1 + 1
= T(n-3) + T(n-4) + 1 + 1 + 1
= T(n-4) + T(n-5) + 1 + 1 + 1 + 1
T(n) = T(n-i) + T(n-i-1) + i
= T(n-(n-i)) + T(n-(n-1-1)) + (n-1)
= T(n-n+1) + T(n-n+2) + (n-1)
= T(1) + T(2) + (n-1)
= 0 + 1 + (n-1)
= 1 + (n-1) ∈ O(n)
i = n-1
Sehingga ,
T(n) = T(n-1) + T(n-2) + 1
= T(n-2) + T(n-3) + 1 + 1
= T(n-3) + T(n-4) + 1 + 1 + 1
= T(n-4) + T(n-5) + 1 + 1 + 1 + 1
T(n) = T(n-i) + T(n-i-1) + i
= T(n-(n-i)) + T(n-(n-1-1)) + (n-1)
= T(n-n+1) + T(n-n+2) + (n-1)
= T(1) + T(2) + (n-1)
= 0 + 1 + (n-1)
= 1 + (n-1) ∈ O(n)
2. Contoh kasus perpangkatan dimana an
(a bilangan bulat dan n > 0)
function Pangkat (input a, n : integer) → integer
Algoritma :
if
n = 0 then
return
1
else
return a * Pangkat(a, n-1)
endif
endfunction
Operasi dasar utama : -
Rekurens : Pangkat(n-1)
Penghenti : T(1) = 0
Rekurens : Pangkat(n-1)
Penghenti : T(1) = 0
Permisalan :
T(n-1) = T(n-1) + 1 T(n-i) → T(1)T(n-2) = T(n-2) + 1 n-i = 1
T(n-3) = T(n-3) + 1 -i = 1-n
i = n-1
Sehingga,
T(n) = T(n-1) + 1
= T(n-2) + 1 + 1
= T(n-3) + 1 + 1 + 1
T(n) = T(n-i) + i
= T(n-(n-1) + (n-1)
= T(n-n+1) + (n-1)
= T(1) + (n-1)
= 0 + (n-1)
= n-1 ∈ O(n)
3. Contoh kasus mencari faktor persekutuan besar
function FPB (input m, n: integer) → integer
Algoritma :
if (m=0) then
FPB ← n
else if
(m < n) then
FPB ← FPB (n, m)
else
FPB ← FPB (m mod n, n)
endif
endif
endfunction
Operasi dasar utama : mod
Rekurens : FPB(m mod n)
Pengehenti : m < n
a. jika m=0 maka n adalah FPB.
b. jika m<n maka m adalah FPB (m,n) ; berhenti.
c. jika tidak maka masuk ke langkah selanjutnya.
d. m dibagi dengan n dan dimisalkan r adalah sisanya.
e. ganti nilai m dengan nilai n dan nilai n dengan r, lalu ulangi ke langakah 1.
Contoh :
Karena sisa terakhir adalah nol maka FPB dari 312 dan 70 adalah sisa sebelumnya yaitu 2.
Operasi dasar utama : mod
Rekurens : FPB(m mod n)
Pengehenti : m < n
a. jika m=0 maka n adalah FPB.
b. jika m<n maka m adalah FPB (m,n) ; berhenti.
c. jika tidak maka masuk ke langkah selanjutnya.
d. m dibagi dengan n dan dimisalkan r adalah sisanya.
e. ganti nilai m dengan nilai n dan nilai n dengan r, lalu ulangi ke langakah 1.
Contoh :
Karena sisa terakhir adalah nol maka FPB dari 312 dan 70 adalah sisa sebelumnya yaitu 2.
[n log r
= log rn < log Fn < log N => nlogN/logr ∈ O(logN)]
Kompleksitas waktu logaritmik ini berarti, laju pertumbuhan waktunya lebih lambat
dari pada pertumbuhan n
Kompleksitas waktu logaritmik ini berarti, laju pertumbuhan waktunya lebih lambat
dari pada pertumbuhan n