Sunday, November 27, 2016

Kompleksitas waktu untuk algoritma rekursif

Contoh 1. Algoritma rekursif menghitung Faktorial

program faktorial;

kamus
n:integer;

function faktorial(n:integer):integer
 if n = 1 then
  faktorial <-- 1
 else
  faktorial <-- n * faktorial(n-1)
endfunction

algoritma
input (n)
output(faktorial(n))   

Operasi dasar :

Operasi Dasar
Tmax
Tmin
<--
n
1
*
n-1
0
-
n-1
0
=
n
1

Opersi dasar (*)
Tn = n-1

Contoh 2. Algoritma rekursif menghitung pangkat

Program hitung_pangkat;

kamus
bil,p:integer;

function pangkat(bil,p:integer):longint;

 if p=0 then
   pangkat <-- 1
 else
   pangkat <-- bil*pangkat(bil,p-1)

endfunction


Algoritma
   input(bil) {input bilangan}
   input(p) {input nilai pangkat}
  Output('pangkat(bil,p))
end.  

Operasi Dasar
Tmax
Tmin
<--
n
1
*
n-1
0
-
n-1
0
=
n
1

Opersi dasar (*)
Tn = n-1


Contoh 3. Algoritma rekursif menghitung Deret

program Hitung_Deret;

kamus
 n:integer

function deret(n:integer):integer

 if n=1 then
   deret <-- 1
 else
   deret <-- n + deret(n-1)

endfunction


Algoritma

   Input (n)
   Output (deret(n));
  
end.

Operasi Dasar
Tmax
Tmin
<--
n
1
+
n-1
0
-
n-1
0
=
n
1

Opersi dasar (+)
Tn = n-1