Efisiensi Algoritma

Analisa yang paling sering dilakukan pada suatu algoritma adalah waktu proses. Menentukan waktu proses secara tepat merupakan pekerjaan yang sangat sulit karena waktu proses secata eksak sangat terhgantung pada implementasi algoritma dan perangkat keras yang dipakai. Analisa yang di inginkan untuk menyatakan efisiensi algoritma haruslah dibuat se umum mungkin sehingga bias dipakai  pada semua algoritma, terlepas dari implementasi dan juga compiler yang di pakai maupun perangkat keras yang digunakan. Akbiatnya analisa tidak dipakai pada waktu proses secata eksak. Kompleksitas algoritma cukup di nyatakan dalam order waktu proses (Big-Oh) secara fungsi jumlah data masukan yang diberikan. Dalam analisa tersebut kita menfokuskan diri pada operasi aktif yang merupakan pusat algoritma, yaitu bagian algoritma yang paling sering di eksekusi. Bagian-bagian lain seperti pemasukan data,penugasan (asigment), dan lain-lain dapat diabaikan karena bagian-bagian tersebut tidak sesering operasi aktif. Jumlah eksekusi operasi aktif itulah yang selanjutnya dihitung

Contoh

Perhatikan potongan program beikut ini yang menghitung jumlah n buah suatu bilangan ril

Carilah operasi aktif program tersebut dan nyatakan order waktu dalam proses sebagai fungsi jumlah masukan (n)

Penyelesaian

Untuk mencari  operasi aktif, haruslah di tentukan beberapa kali program eksekusi pada tiap-tiap bagian.

• Bagian a, eksukusi satu kali

• Bagian b, merupakan bagian loop, kalang itu akan dip roses berdasarkan kenaikan harga I dari i=1             hingga i=n.jadi statement  sum=sum+v[i] akan dip roses sebanyak n kali sesuai dengan kenaikan harga i

• Bagian c, akan di proses sekali

Oleh karena bagian b merupakan bagian yang paling sering dip roses, maka bagian b merupakan operasi aktif. Bagian a dan c dapat diabaikan karena bagian-bagian tersebut tidak dip roses sesering bagian b

Banyak kali bagian b diproses sama dengan banyak data yang dimasukan (=n). dengan demikian, program penjumlahan n buah bilangan rill memiliki order sebanding dengan n. dengan kata lain program memiliki O(n).

Contoh 12.7

Carilah order waktu proses bagian-bagian program berikut ini

a.  for i=2 to n

A=2*n +i*n

End for

b. for i=1 to n

for j=1 to i

A=n+i*j

End for

End for i

c. for i=[n/2] to n

A=n-1

End for i

Penyelesaian

Jumlah penyelesaian statement  A=a*n+1*n mengikuti iterasi dalam I, yaitu dari i=2 hingga i=n. jadi sebanyak (n-2) + 1=(n-1) kali. Perhatikan bahwa  yang dipentingkan disini bukanlah berapa banyak nilai variable A tetapi frekuensi pemrosesan A, jadi Algoritma memiliki order O(n)

Pada

I=1, j berjalan 1 hingga 1 sehingga A dip roses 1 kali

I=2, j berjalan 1 hingga 2 sehingga A dip roses 2 kali

I=3, j berjalan 1 hingga 3 sehingga A dip roses 3 kali

Dan seterusnya

I=n, j berjalan 1 hingga n sehingga A di proses sebanyak n kali