Contoh Analisis Matematis Algoritma Rekursif :
Menghitung Faktorial
Function
F(input awal,n : integer) à
real
KAMUS:
fak : real
ALGORITMA:
If n = 0 then
fak <-- 1
else
fak <-- n * F(n-1)
endif
return fak
endFunction
T(n) ---- 0 , n = 0
T(n) ---- T
(n-1) +1 , n > 0
T(n)
= 1 + T(n-1)
= 1 + 1 + T (n-2) = 2 + T (n-2)
= 2 + 1 + T (n-3) = 3 + T (n-3)
= …
= n + T(0)
= n + 0
Jadi
T(n) = n ϵ Ο(n)
======================================
Mencari Nilai S
Algortihm S(n)
{input : A positive integer n}
{Output : the sum of the first n cubes}
if n=1 then
return 1
else
return S(n-1) + n * n* n
endif
T(n) ---- 0 , n = 0
T(n) ---- T
(n-1) +2 , n > 0
T(n)
= 2 + T(n-1)
= 1 + 2 + T (n-3) = 3 + T (n-3)
= …
= n + T(0)
= n + 0
Jadi
T(n) = n ϵ Ο(n)
======================================
Menghitung
Deret Aritmatika
Function
F(input n : integer) à real
KAMUS
deret
: real;
ALGORITMA
if
awal = 0 and n = awal+1 then
deret <-- 1;
else
deret <-- n + F(n-1);
endif
return deret
endFunction
Paling Dalam : +
+ : n
F(n)
= n + F(n-1) untuk n > 1
F(n)
= 1 untuk n = 1 dan n=0
T(n)
= 1 + T(n-1)
T(n)
= 1 + 1+ T(n-2) = 2 + T(n-2)
T(n)
= 2 + 1 + T(n-3) = 3 + T(n-3)
T(n)
= …..
T(n)
= n + 0
T(n) = n
T(n)
= n ϵ O(n)
