42
m
2.
f
(n) adalah
T( g (n)) jika
dan
hanya
jika
f
(n) adalah
?( g (n)) dan
f
(n)
adalah
O( f (n))
?
Teorema 4
Jika
A(n) =
a
m
n
+
a
m-¹
n
m-¹
+
....
+
a1
n
+
a
0
adalah
sebuah
polinomial
yang
memilki
derajat m maka
A(n) = ?(n
m
)
.
Hal
ini
menunjukkan
bahwa
suku
yang
berderajat
lebih
tinggi
mendominasi
suku
yang
lebih
rendah,
artinya
laju
pertambahan
waktunya
akan
lebih besar
jika
derajatnya
lebih
tinggi,
f
(n) akan mendominasi
T
(n) jika T (n) sama dengan
?( f (n)) .
?
Teorema 5
Misalkan T1 (n) =
?( f (n)) dan T
2
(n) = ?( g (n)) maka :
1. T1 (n) + T2 (n) = ?( f (n)) + ?( g (n)) = ?(max( f (n), g (n))
2. T1 (n) * T2 (n) = ?( f (n)) * ?( g (n)) = ?( f (n) * g (n))
3.
(c * f (n)) = ?( f (n)), c merupakan suatu konstanta
4. f (n) = ?( f (n))
2.10
STD (State Transition Diagram)
STD
merupakan suatu modelling tool yang menggambarkan sifat
ketergantungan pada waktu di sistem. Pada
mulanya STD hanya digunakan untuk
menggambarkan
suatu
sistem yang
memiliki
sifat
real
time,
seperti
process
control,
telephone switching system, high speed data acquisition, dan
lain-lain. Pada STD
terdapat
dua
macam
kerja,
yaitu
:
passive
dan
active.
Passive
adalah
sistem yang
melakukan
kontrol
terhadap
lingkungan,
tetapi
lebih
bersifat
memberikan
reaksi
atau
 |