Algoritma yang
telah dibangun seharusnya diperhitungkan nilai Compilasinya . Untuk itu ada 2
hal yang perlu diperhatikan :
1. Running Time
-
Adalah waktu tempuh yang diperlukan
untuk eksekusi program meliputi :
·
banyaknya langkah mulai dari awal sampai
akhir
·
ukuran dan jenis data input yang
dipergunakan
·
jumlah space yang digunakan
Contoh
:
Diketahui
f(n) = a0 + a1 x
+ a2 x2 +
..an Xn
Waktu
tempuh T(n) = O ( f(n)) dibaca Big Oh
T(n) = O ( Xn )
ΰ
Waktu tempuh untuk statement
sederhana spt read,write, assignment : T(n) = O (1)
ΰ
Waktu
tempuh untuk for
do
Contoh
:
For
i = 1 to n do
Begin
Data[1] = x ;
C [1 ] = O . O ;
End .
Maka
T(n) = O (2n)
T(n) = O (n)
Contoh
lagi :
For
i = 1 to n do
Begin
For j = 1 to n do
Begin
C ( i , j ) = O.O ;
A ( i , j ) = O.O ;
B ( i , j ) = O.O ;
End;
End.
Maka running time-nya ialah :
T ( n )
= O( 3m (n))
=
O( 3 mn )
T ( n )
= O ( mn )
ΰ
waktu
tempuh untuk bentuk if
then
if
< condition > then
begin
statement 1
=
=
statement n
end;
else
begin
statement 1
=
=
statement n
end;
end.
-
jika
< condition > tidak memanggil procedure / function maka T (n) = O (1)
-
jika
< statement 1
n > :
·
pada bagian if T (n) = O (
f(n))
·
pada bagian else T (n) = O ( g(n))
dan O ( f(n) Ή O , O
(g(n)) Ή O ,
maka ada 3 kemungkinan. Yaitu :
a.
jika
f(n) = O ( g(n)) maka T (n) = O (
g(n))
b.
jika
f(n) = O ( f(n)) maka
T (n) = O ( f(n))
c.
jika
f(n) Ή O (
g(n)) dan g(n) Ή O ( f
(n)) maka T(n) = O ( max ( f(n),g(n))
ΰ
waktu
tempuh untuk bentuk while
..do
untuk
< condition > do
begin
< while part statement 1 >
=
=
< while part statement
n >
end.
·
jika waktu tempuh ( while part statement
) T(n) = O ( f(n)) dan batas atas waktu tempuh dari < condition > adalah
T(n) = O ( g(n)) dimana g(n) > 1 maka waktu tempuh total T(n)total = O( f(n).
g(n))
ΰ
waktu
tempuh untuk bentuk repeat
until
repeat
( repeat part statement 1 )
=
=
( repeat part statement n )
until < condition >
jika waktu tempuh ( repeat part statement
) adalah T(n) = O ( f(n)) dan batas atas aktu tempuh dari ( condition ) adalah
T(n) = O ( g(n)) dimana g(n), maka total waktu tempuh adalah T(n) = O ( f(n) g(n))
ΰ
waktu
tempuh untuk bentuk for
..
do
for
i = 1 to n do
begin
( statement 1 )
=
=
( statement n )
end
jika waktu
tempuh ( statement ) adalah T(n) = O ( f(n)) dan batas atas waktu tempuh for 1
to n do adalah T(n) = O ( g(n)) dengan g(n) > 1 maka T(n) total = O ( f(n) .
g(n) )
Contoh
soal
Tentukan
Algoritma penjumlah 2 matriks dengan elemen- elemenya bertipe real dengan ukuran
( m * n ) , lakukan analisa dengan Algoritma yang anda buat !
jawab
[
m*n ] + [ m*n ] = [ m*n ]
A
B
C
For
i = 1 to n do
Begin
For
j = 1 to n do
Begin
C ( i , j ) = A ( i , j ) + B ( i , j )
End;
End.
Analisanya :
-
bilangan
real untuk var A, B, C masing- masing bentuk 4 byte
-
operasi
yang dilakukan penjumlahan
-
banyaknya
operasi yang dilakukan untuk baris = m kali
-
banyaknya
operasi yang dilakukan untuk kolom = n kali
-
banyaknya
memori yang digunakan =
·
A = 4mn
·
B = 4 mn
·
C =
4 mn
Conto
soal lagi
Buat
algoritma perkalian 2 matrik yang setiap elemenya bertipe real dengan ukuran
matrik A = m x n
dan
matrik B = n x 2, lakukan analisa anda !
jawab
for
i = 1 to n do
begin
for
j = 1 to n do
begin
C ( 1,1 ) = O.O ;
For k = 1 to 2 do
Begin
C ( i,k ) =
C ( i,k ) + A ( i,j ) * B (
j,k )
End;
End;
End.
Analisa = T ( m,n,k ) = 13mnk