Kompleksitas Algoritma

Algoritma adalah urutan logis langkah-langkah penyelesaian masalah secara sistematis. Sebuah algoritma tidah hanya harus benar saja, tetapi juga harus efisien. Suatu algoritma walaupun benar tidak akan berguna jika waktu dan memori yang di gunakan untuk menjalankan algoritma tersebut terlalu banyak.
Masalah keefesienan (efficiency) algoritma diukur dari : berapa jumlah waktu dan ruang (space) memori yang di butuhkan untuk menjalankan algirtma tersebut. Dimana algoritma yang efisien adalah algoritma yang meminimumkan kebutuhan waktu dan ruang serta memori yang digunakan.

Mengapa Kita Memerlukan Algoritma yang Mangkus(efisien) ?

Misalnya sebuah komputer yang mampu menjalankan program dengan masukan berukuran n dalam waktu 10-4 x 2^n detik.
Dengan algoritma dan komputer tersebut, maka dapat dihitung bahwa untuk

n=10, dibutuhkan waktu eksekusi kira-kira 1/10 detik
n=20, dibutuhkan waktu eksekusi kira-kira 2 menit
n=30, dibutuhkan waktu eksekusi lebih dari satu hari

misalkan kita dapat menjalankan komputer tanpa gangguan selama satu tahun, maka waktu satu tahun itu hanya dapat menyelesaikan persoalan dengan masukan sebanyak 38.

Karena kita perlu menyelesaikan masalah dengan jumlah yang lebih besar, mukin kita harus membeli mesin baru yang 100 kali lebih cepat dari pada komputer semula (menjadi 10^-6). Dengan algorima yang sama, kita sekarang dapat menyelesaikan masalah denga masukan sebanyak n dalam waktu 10^-6 x 2^n detik. Bila kita menjalan kan mesin baru itu selama satu tahun penuh, kita hanya dapat menyelesaikan persoalan untuk masukan sebanyak n selama selang waktu tertentu, komputer baru itu akan dapat menyelesaikan persoalan dengan masukan paling banyak n + 7 dalam waktu yang sama.

Sebagai gantinya kita memutuskan untuk menaruh perhatian padan algoritmanya. Misalkan kita menemukan sebuah algrotima baru yang dapat menyelesaikan masalah semula dalam waktu orde kubik (n^3). Bayangkan lah dengan menggunakan komputer pertama, algoritma baru ini dapat menyelesaikan masalah dengan masukan sebanyak n dalam dalam waktu 10^-4 x n^3 detik. Dalam waktu satu hari kita dapat menyelesaikan masalah dengan jumlah masukan lebih besar dari 900; dan dalam waktu satu tahun komputasi ukuran masukan yang dapat diselesaikan hampir mencapai 6800 lebih bahkan dengan komputer yang kedua jumlah masukan yang dapat diproses selama satu tahun komputasi mejadi lebih banyak lagi banyak lagi, yaitu 31.500 lebih.

Hal ini diperlihatkan pada gambar dibawah ini. Jelaslah bahwa algoritma kedua lebih mangkus yang berarti lebih bagus dibandingkan degan algitma pertamanya.


Kita dapat mengukur waktu yang diperlukan oleh sebuah algoritma dengan menghitung banyaknya operasi/instruksi yang dieksekusi.

Jika kita mengetahui besaran waktu (dalam satuan detik) untuk melaksanakan sebuah operasi tertentu, maka kita dapat menghitung berapa waktu sesungguhnya untuk melaksanakan algoritma tersebut.

Contoh 1. Menghitung rata- rata

a1 a2 a3 … an

Larik bilangan bulat

Kita lihat procedure berikut ini

procedure HitungRerata(input a1, a2, ..., an : integer, output r : real)
{ Menghitung nilai rata-rata dari sekumpulan elemen larik integer a1, a2, ..., an.
Nilai rata-rata akan disimpan di dalam peubah r.
Masukan: a1, a2, ..., an
Keluaran: r (nilai rata-rata)
}
Deklarasi
k : integer
jumlah : real

Algoritma
jumlah←0
k←1
while k ← n do
jumlah←jumlah + ak
k←k+1
endwhile
{ k > n }
r ← jumlah/n { nilai rata-rata }

banyaknya operasi/instruksi
(i) Operasi pengisian nilai (jumlah←0, k←1, jumlah←jumlah+ak, k←k+1, dan r ← jumlah/n)
Jumlah seluruh operasi pengisian nilai adalah
t1 = 1 + 1 + n + n + 1 = 3 + 2n

(ii) Operasi penjumlahan (jumlah+ak, dan k+1)
Jumlah seluruh operasi penjumlahan adalah
t2 = n + n = 2n

(iii) Operasi pembagian (jumlah/n)
Jumlah seluruh operasi pembagian adalah
t3 = 1
Total kebutuhan waktu algoritma HitungRerata:

t = t1 + t2 + t3 = (3 + 2n)a + 2nb + c detik

Model perhitungan kebutuhan waktu seperti di atas kurang dapat diterima:
1. Dalam praktek kita tidak mempunyai informasi berapa waktu sesungguhnya untuk melaksanakan suatu operasi tertentu

2. Komputer dengan arsitektur yang berbeda akan berbeda pula lama waktu untuk setiap jenis operasinya.

Selain bergantung pada komputer, kebutuhan waktu sebuah program juga ditentukan oleh compiler bahasa yang digunakan.

Model abstrak pengukuran waktu/ruang harus independen dari pertimbangan mesin dan compiler apapun. Besaran yang dipakai untuk menerangkan model abstrak pengukuran waktu/ruang ini adalah kompleksitas algoritma.