3. Kompleksitas Algoritma (Ruang dan Waktu)

Summary:silahkansaja

Kita memerlukan suatu cara untuk mengukur apakah sebuah algoritma lebih baik jika dibandingkan dengan algoritma yang lain untuk menyelesaikan permasalahan yang sama. Oleh karena itu kita bahas teori kompleksitas dari sebuah algoritma.


Kompleksitas dapat kita bagi menjadi dua: kompleksitas waktu dan kompleksitas ruang. Kompleksitas waktu adalah waktu yang dibutuhkan oleh komputer untuk menjalankan sebuah algoritma sampai selesai. Kompleksitas ruang adalah memori yang dibutuhkan oleh komputer untuk menjalankan sebuah algoritma sampai selesai.


Kompleksitas Ruang


Perhatikan contoh dibawah ini:


Algorithm hitung(x,y,z)
{
return x+y*z+(x+y-z)/(y+z) +13
}


Algorithm jumlah(a,n)
//a adalah array dengan ukuran n
{
s:=0.0;
for i=1 to n do
s:=s+a[i];
return s;
}
Memori yang dibutuhkan untuk menjalankan algoritma diatas bergantung pada jumlah dari:
1. Bagian yang konstan dan tidak tergantung pada input dan output. Bagian ini biasanya terdiri dari memori yang dibutuhkan untuk sourcecode, variable aggregate, konstanta, dll.
2. Bagian variabel yang kebutuhan memorinya bergantung pada instans permasalahan yang hendak diselesaikan. Kita sebut bagian ini sebagai karakteristik instans.


Dengan demikian kompleksitas ruang dapat dirangkum dalam persamaan:
S(P) = c + Sp, dimana c adalah konstanta dan Sp adalah karakteristik instans.


Dalam analisa kompleksitas ruang, kita hanya akan memperhitungkan Sp dan tidak terlalu terfokus pada konstanta c. Pada algoritma hitung diatas, karakteristik instans ditentukan oleh x,y dan z. Dengan asumsi masing masing x,y,z dan return value bisa disimpan dalam 1 word (16 bits), maka dapat kita lihat bahwa memori yang dibutuhkan oleh algoritma hitung tidak tergantung pada karakteristik instans x,y dan z, dengan demikian Sp = 0.


Pada algoritma jumlah, karakteristik instans ditentukan oleh n (jumlah elemen yang akan dipanggil). Karena variabel a harus mampu menampung float sejumlah n elemen, maka memori yang dibutuhkan adalah n word. Variable s, i dan n masing-masing membutuhkan 1 word. Dengan demikian kita dapatkan pertidaksamaan Sp[jumlah](n) >= (n+3).




Kompleksitas Waktu


Total waktu yang dibutuhkan oleh sebuah program adalah jumlah dari kebutuhan waktu kompilasi dan kebutuhan waktu eksekusi. Kita akan memfokuskan diri pada waktu eksekusi karena program biasanya hanya dikompilasi sekali dan dijalankan berulang-ulang. Karena waktu yang dibutuhkan untuk mengeksekusi sebuah program bergantung pada banyak faktor dan sulit untuk dijalankan, maka yang dapat kita lakukan adalah melakukan pendekatan yang salah satunya adalah dengan menghitung jumlah langkah. Langkah disini kita definisikan sebagai bagian dari program yang memiliki waktu eksekusi yang tidak tergantung pada karakteristik instans.


Untuk menghitung jumlah langkah, kita akan menggunakan variable hitung yang dimulai dengan nilai 0 dan terus bertambah dengan bertambahnya jumlah langkah. Untuk lebih jelasnya kita akan menggunakan variable hitung pada algoritma jumlah diatas sehingga akan terlihat sebagai berikut:


Algorithm jumlah(a,n)
{
s:=0.0;
hitung:=hitung+1; //kita tambah 1 pada nilai hitung untuk assignment s

for i=1 to n do
{
hitung:=hitung+1; //untuk "for i"
s:=s+a[i];
hitung:=hitung+1; //untuk assignment s
}
hitung:=hitung+1; //untuk akhir dari "for i"
hitung:=hitung+1; //untuk return
return s;
}


Jika kita hanya memperhitungkan hitung, maka algoritma diatas dapat kita sederhanakan menjadi:
Algorithm jumlah(a,n)
{
for i=1 to n do
hitung:=hitung+2;
hitung:=hitung+3;
}


Dengan demikian jumlah langkah untuk algoritma hitung diatas adalah 2n+3.


Kompleksitas Algoritma (Ruang dan Waktu) Originally published in Shvoong: http://id.shvoong.com/internet-and-technologies/software/2063318-kompleksitas-algoritma-ruang-dan-waktu/