10
2.1.3
Kompleksitas Algoritma, Waktu, Dan Masalah
Kompleksitas dari suatu algoritma merupakan ukuran seberapa
banyak komputasi yang dibutuhkan algoritma tersebut untuk mendapatkan
hasil yang diinginkan. Algoritma yang dapat memperoleh hasil yang
diinginkan dalam waktu yang singkat memiliki kompleksitas yang rendah,
sementara algoritma yang membutuhkan waktu yang lama untuk memperoleh
hasil tersebut mempunyai kompleksitas yang tinggi.
Biasanya kompleksitas algoritma dinyatakan secara asimptotik dengan
notasi big-O. Jika kompleksitas waktu untuk menjalankan suatu algoritma
dinyatakan dengan T(n),
dan memenuhi
T(n)
= C(f(n))
untuk
n
= n
0,
maka kompleksitas dapat dinyatakan dengan
T(n) = O(f(n)).
Salah satu ukuran biaya dalam pengeksekusian sebuah algoritma
adalah lamanya waktu yang diperlukan. Pengukuran waktu yang diperlukan
dalam mengeksekusi suatu algoritma dinamakan kompleksitas waktu
algoritma tersebut (Liu, C.L, 1995, p272).
Dua buah algoritma yang berbeda dapat digunakan memecahkan
masalah yang sama dan mungkin saja, mempunyai kompleksitas waktu yang
sangat berbeda (Liu, C.L, 1995, p274). Kompleksitas waktu algoritma terbaik
untuk memecahkan masalah tersebut dinamakan sebagai kompleksitas waktu
suatu masalah (Liu, C.L, 1995, p277).
Ada dua buah klasifikasi permasalahan (Leahy, Billy., 2000, p21-24),
yaitu sebagai berikut :
1.
Permasalahan yang dapat dipecahkan (decidable / solvable problem)
permasalahan yang termasuk klasifikasi ini adalah semua jenis
permasalahan yang mempunyai algoritma solusi, walaupun kadang kala
 |