40
x
=
x
+
y
for (i = 1;
i
+
+; i <=
n)
{
x
=
x
+
y
}
for (i = 1;
i
+
+; i <=
n)
{
for (i = 1;
i
+
+; i <=
n)
{
x
=
x
+
y
}
}
(a)
(b)
(c)
Pada
program
(a)
hanya
terdiri
dari
x
=
x
+
y
,
artinya
instruksi
hanya
dijalankan
satu
kali
dan
nilai
kompleksitasnya
adalah
1.
Sedangkan
pada
program
(b)
instruksi
dijalankan
sebanyak
n kali
dan
nilai
kompleksitasnya
adalah
n dan
pada
program (c)
perintah dijalankan sebanyak
n
2
,
sehingga
nilai kompleksitasnya adalah
n
2
.
Nilai-nilai
1, n, n
2
disebut
dengan
order
of
magnitude.
Nilai
kompleksitas
waktu
dapat
dinyatakan
dalam bentuk
notasi
matematik
yaitu
:
T, O, ?
yang disebut
asymtotic notation. Notasi
T
merupakan
fungsi
yang
menyatakan
kompleksitas
waktu
dari
suatu
instruksi.
Jika
terdapat dua
fungsi kompleksitas
waktu
yaitu
f
(n)
dan
g
(n) , dapat dinyatakan bahwa
f
(n)
adalah
T( g (n)) .
Jika
terdapat
suatu
nilai
riil
positif
c1 dan
c2 dan
sebuah
nilai
positif
integer
n
0
sedemikian sehingga
c1
.g (n) =
f
(n) = c2 .g (n) untuk semua
n
>
n
0
.
Jadi
dapat
disimpulkan
jika
f
(n)
adalah
T( g (n)) ,maka
g
(n)
merupakan
fungsi
batas
atas
dan batas bawah dari
f
(n) ,yang berarti kondisi terbaik (batas bawah) dan kondisi
terburuk
(batas
atas)
memiliki
suatu
nilai
waktu
yang
sama
yaitu
pada
suatu
faktor
konstan.
Notasi
O
meyatakan
batas
atas
dari
kompleksitas
waktu
dari
suatu
instruksi.
Jika
terdapat
dua
fungsi
kompleksitas
waktu
yaitu
:
f
(n)
dan
g
(n) ,
dapat
dinyatakan
bahwa
f
(n)
adalah
O( g (n)) . Jika terdapat suatu nilai riil konstan
c
>
0
dan sebuah nilai
positif
integer
n
0
,
sedemikian sehingga
f
(n) = c.g (n) untuk semua
n
>
n
0
.
Artinya jika
 |