Konsep Analisa Algoritma

aturan umum analisa algoritma

Secara umum, running time pada sebuah statemen atau kelompok statemen mungkin terparameterisasi dengan ukuran input dan atau dengan banyak variabel. Parameter yang diperbolehkan untuk running time pada keseluruhan program adalah n ukuran input. Aturan umum untuk analisa algoritma adalah sebagai berikut :

1. Running time setiap assignment ( tugas , baca (read) dan statemen Write) besarnya dapat diambil O(1)
2. running time pada barisan statemen ditentukan dengan aturan jumlahan yaitu bahwa running time pada barisan adalah tidak melebihi dari sebuah faktor konstan yang merupakan running time terbesar pada beberapa statemen barisan.
3. running time pada statemen if adalah harga pada kondisi statemen eksekusi. Waktu menghitung kondisi secara normal adalah O(1). Waktu untuk if then else adalah waktu menghitung kondisi ditambah waktu terbesar yang dibutuhkan untuk statemen eksekusi jika kondisinya false (salah).
4. waktu eksekusi adalah jumlah semua waktu sekitar loop, waktu eksekusi sekumpulan statemen dan waktu mengevaluasi kondisi untuk penghentian (biasanya yang terakhir adalah O(1)).

Untuk selanjutnya f(x) disebut pula dengan T(n) atau running time.

Contoh Analisa Algoritma Sorting

Diberikan prosedur program sebagai berikut :

Procedure select(T[1..n])

for i ¬ 1 to n – 1 do

minj ¬ i; minx ¬ T[i]

for j ¬ i + 1 to n do

if T[j] < minx then minj ¬ j

minx ¬ T[j]

T[minj] ¬ T[i]

T[i] ¬ minx

Endif

Endfor

endfor

Meskipun waktu yang diperlukan oleh setiap perputaran didalam loop bukan konstan, waktu tersebut adalah dibatasi oleh suatu konstanta c. untuk setiap nilai pada, instruksi didalam loop yang dieksekusi adalah n – (i +1) + = n-i kali, dan selanjutnya waktu yang diberikan oleh loop terdalam adalah t(i) < (n-i) c.

Waktu yang diberikan oleh putaran ke-I pada loop terluar dibatasi oleh b + t(i) untuk sebuah konstanta b memberikan jumlahan pada operasi – operasi dasar sebelum dan sesudah loop terdalam dan loop control untuk loop terluar.

Selanjutnya, total waktu yang diperlukan oleh algoritma diatas adalah

_{n-1 n-1 n-1}

b + (n-i) c = (b+c n) –c i

_{i = 1 i=1 i=1}

= (n-1) (b+c n) – c n ( n – 1) / 2

= 1 c n² + b – 1 c n – b

2 2

Adalah O(n²).

Konsep Analisa Algoritma

Berdasarkan struktur logika yang terdapat dalam algoritma, maka konsep analisa algoritma dapat didasarkan pada struktur logika tersebut.

Dalam bahasan ini akan diberikan contoh-contoh sehingga akan memudahkan dalam memahami analisa efisiensi algoritma.

n Barisan Sederhana statemen

s₁;

s₂;

s₃;

...

...

...;

s_k

Dimana k adalah suatu konstanta akan menghasilkan O(1)

Contoh : Diberikan algoritma untuk mencari luas persegi panjang, maka :

read(panjang) ----à O(1)

Read(lebar) ----à O(1)

Luas := panjang * lebar -----à O(1)

Write(panjang, lebar, luas) ----à O(1)

Berdasar Teorema 2.2 (maximum rule), maka O(max(1,1,1,1)) = O(1)

n Loop Sederhana

for I ¬ 1 to n to

s₁;

s₂;

s₃;

...

s_n

endfor

Dimana s_i adalah O(1), berdasar teorema 2.2.

– Kompleksitas waktu :

n Untuk loop dilakukan proses sebanyak n kali sehingga menghasilkan O(n), berdasar Teorema 2.3 maka O(n . 1 ) = n O(1) atau O(n)

n Sehingga T(n) = O(n)

n Nested Loop

for I ¬ 1 to n to

for j ¬ 1 to n to

s₁;

s₂;

s₃;

...

s_n

endfor

endfor

n Untuk S_i berdasar Teorema 2.2 menghasilkan O(1)

n Untuk Loop dalam (j) memberikan Kompleksitas O(n)

n Untuk Loop luar (i) memberikan kompleksitas O(n)

n Maka berdasar Teorema 2.3, didapat :

– O(n . n . 1 ) = O(n²) atau n O(n)

n Loop index tergantung dari loop luar

for j ¬ 1 to n to

for k ¬ 1 to j to

s₁;

s₂;

s₃;

...

s_n

endfor

endfor

Berdasar Teorema 2.2 untuk s_i memberikan O(1).

– Loop dalam akan dieksekusi sebanyak :

1, 2, 3, …., n kali

Maka akan digunakan dari deret tersebut akan membuat sebuah deret aritmetika, dan untuk menghitung jumlahan deret tersebut digunakan formulasi :

n Dimana a = u₁ = suku pertama

n B = beda = u_n-u_n-1 = u_n-1-u_n-2= . . . =u₃-u₂=u₂-u₁

n Sehingga, untuk deret 1,2,3,..., n

n a = 1, b = 1, sehingga :

Kompleksitas yang dihasilkan : O(n²)

n Index Loop index tidak linier, misalkan diberikan algoritma seperti berikut ini :

h= 1;

while ( h <= n )

s;
h = 2 * h;

endwhile

h memberikan nilai 1, 2, 4, 8, 16, 32, …, n.

Dikarenakan deret tersebut sangat sulit untuk menentukan jumlah sukunya yang merupakan informasi berapa banyak perulangan terjadi, maka akan dilakukan manipulasi deret untuk menghitung jumlah perulangannya.

Dengan mengeluarkan angka 1 dari deret sehingga akan didapat deret baru sebagai berikut : 2, 4, 8, 16, 32, ...., n.

Untuk memudahkan perhitungan maka akan dimanipulasi menjadi deret 1 , 2 , 3, 4, . . .

Sehingga : deret 2, 4, 8, 16, 32, . . . , n dirubah menjadi deret :

Log₂ 2, Log₂ 4, Log₂ 8, Log₂ 16, . . . , Log₂ n; dimana deret tersebut sama dengan deret :

1, 2, 3, 4, . . . , Log₂ n.

Dari deret tersebut, maka dapat dihitung jumlah perulangan terjadi adalah sebanyak Log₂ n, dengan masih menyisakan angka 1 yang dikeluarkan dari deret asal.

Dengan memasukkan 1 proses perulangan, Maka akan diperoleh iterasi total sebanyak 1 + log₂n

Sehingga, Kompleksitas yang dihasilkan adalah O(log n)