1.
Algoritma Menghitung Nilai x Pangkat y
Program Pangkat
Kamus
x,y : integer
Function pangkat (x:integer,
y: integer)
Algoritma
if y = 0 then
return 1
else
return x*pangkat(x,y-1)
endif
endfuction
algoritma
input x,y
output pangkat(x,y)
Analisis:
- Kompleksitas waktu diukur dari
jumalh operasi perkalian (*)
- Jika y = 0 maka pangkat sama dengan 1
(tidak ada operasi perkalian) {basis}
-
Jika y > 0 maka,
pangkat(x,y) = x * pangkat(x,y-1) atau xy
= x * xy-1 (ada operasi perkalian) {rekurens}
- Yang mempengaruhi jumlah
pemanggilan rekursif adalah nilai y atau (y-1) atau T(n-1)
T(n) = 1 + T(n-1) ; n > 0 {rekurens}
T(n) = 1 ; n = 0 {basis}
T(n) = 1 + T(n-1)
=
1 + 1 + T(n-2)
=
2 + 1 + T(n-3)
…
T(n) = n + T(0)
Jadi
T(n)= n ≈ O(n)
2.
Algoritma Menentukan Deret bilangan Fibonacci ke-n
Function fib (input n : integer) → integer
Deklarasi
-
Algoritma
If
(n = 0) or (n = 1) then
Return
n
Else
Return
fib(n-1) + fib(n-2)
endif
Analisis:
- Kompleksitas waktu diukur dari
jumalh operasi samadengan (=)
n = 0 atau n = 1 {basis}
fib(n-1) + fib(n-2) {rekurens}
- T(n)= 2 + T(n-1) + T(n-1) ; n
> 1 {rekurens}
T(n)= 1 ; n = 0 = 1 {basis}
T(n-1)≈T(n-2)
T(n) = 2T(n-1) + 2
=
2{2T(n-1)+2}+2
=
4T(n-2)+6 ; k=2 , C=2
=
8T(n-3)+14 ; k=3 , C=2
…
T(n) = 2kT(n-k)+(2k-1)C
(n-k) = 0 → k=n
T(n) = 2nT(0)+(2n-1)C
T(n) = (1+C)*2n-C
Jadi T(n)≈ 2n ≈ O(2n)
3.
Algoritma
Procedure MinMaks2(input
A : TabelInt, i, j : integer, output min, maks : integer)
{
Mencari nilai maksimum dan minimum di dalam tabel A yang berukuran n elemen
secara Divide and Conquer. Masukan: tabel A yang sudah terdefinisi
elemenelemennya Keluaran: nilai maksimum dan nilai minimum tabel }
Deklarasi
min1, min2, maks1, maks2 : integer
Algoritma
if i=j then
{ 1 elemen }
min ← Ai
maks ← Ai
else
if (i = j-1) then
{ 2 elemen }
if Ai < Aj then
maks ← Aj
min ← Ai
else
maks ← Ai
min ← Aj
endif
else { lebih dari 2
elemen }
k ← (i+j) div 2 { bagidua tabel pada posisi k } MinMaks2(A,
i, k, min1, maks1)
MinMaks2(A, k+1, j,
min2, maks2)
if min1 < min2 then
min ← min1
else
min ← min2
endif
if
maks1<maks2 then
maks ← maks2
else
maks ← maks2
endif
Analisis:
T(n) = 0; n=1 {basis}
T(n) = 1; n=2 {basis}
T(n) = 2T(n/2)+2 ; n>2 {rekurens}
Asumsi n = 2k, dengan
k bilangn bulat positif, maka:
T(n) = 2T(n/2)+2
=
2(2T(n/4) + 2) + 2 = 4T(n/4) + 4 + 2
=
4 (2T(n/8) + 2) + 4 + 2 = 8T(n/8) + 8 + 4 + 2
=
... k-1
=
2k – 1 T(2) + ∑ 2i
i=1
=
2k – 1 1 + 2k – 2
=
2(2logn)-1 + 2(2logn)-2
=
n/2 + n-2
=3n/2-2
Jadi T(n) = n = O(n)
resource :
buku Algoritma dan Pemrograman, Renaldi Munir
Terima kasih banyak kakak
ReplyDeleteSaya dapat pencerahan yang bagus dari sini :)