31
2.4.3
Kompleksitas Algoritma
Menurut
Horowitz
(1998,
p33),
mengetahui
kompleksitas suatu
program
sangat
menentukan
dalam
menentukan
berapa
kebutuhan
waktu untuk
memproses
suatu
algoritma. Asumsikan
jika
terdapat
dua
program (P
dan
Q),
dimana P
memiliki kompleksitas O(n) dan Q
memiliki kompleksitas O(n²),
maka
dapat dipastikan kalau P akan lebih cepat dari Q untuk nilai n yang cukup besar.
Namun
dalam
menentukan kompleksitas
mana
yang
akan
dipilih,
kita
perlu
mengetahui berapa nilai n
yang akan kita
temukan. Contohnya, jika
program
P
berjalan
dalam
kecepatan
10
6
n
miliseconds,
sedangkan
program
Q
berjalan
dalam
kecepatan
2
n
miliseconds,
maka
jika
nilai
n
adalah
=
10
6
,
dan
kondisi
yang
lainnya adalah sama, program
yang
lebih baik adalah program Q.
Berikut adalah tabel pertumbuhan fungsi n.
Tabel 2.2 Fungsi Pertumbuhan n
Log n
n
n log n
n²
n³
2
n
0
1
0
1
1
2
1
2
2
4
8
4
2
4
8
16
64
16
3
8
24
64
512
256
4
16
64
256
4.096
65.536
5
32
160
1.024
32.768
4.294.967.296
 |