Algoritma dan Struktur Data. Performansi Algoritma

Algoritma dan Struktur Data

Performansi Algoritma

Teknik Informatika Universitas Muhammadiyah Malang 2016

Mana yang lebih baik? • pilihan 1 : Algoritma biasa dengan komputer yang cepat. • pilihan 2 : Menggunakan algoritma yang efisien dengan komputer standart.

Studi Kasus 1. Algoritma dengan waktu eksekusi dalam orde n eksponensial 2 2. Sebuah komputer yang mampu menjalankan program dengan masukan n dalam waktu -4 10 detik. n = jumlah data.

Penyelesaian Dapat dihitung T(n) dari persamaan 10-4 x 2n : • n = 10, waktu eksekusi kurang lebih 1/10 detik. • n=20, waktu eksekusi kurang lebih 2 menit. • n=30, waktu eksekusi lebih dari satu hari. • Semakin banyak data yang diproses, waktu yang dibutuhkan semakin lama.

Efficiency Hardware • Jika-6 kecepatan komputer di-upgrade sebesar 100 kali ( 10 ). Maka dengan algoritma yang sama : -6 n jumlah masukan = n, waktu = 10 x 2 detik. n=35, waktu yang dibutuhkan kurang lebih 9,5 jam.

Efficiency Algorithms • Misal ada algoritma baru yang dapat menyelesaikan masalah tsb dalam orde kubik 3 ( n ) • Dengan menggunakan komputer pertama waktu -4 3 yang dibutuhkan 10 x n detik. • Sehingga : hanya dengan waktu 1 hari data yang dapat diproses sebanyak n = 900.

Efficiency Algorithms KOMPUTER 1 Algoritma 1 Algoritma 2

Waktu 1 hari 1 hari

n 30 900

KOMPUTER 2 Algoritma 1 Algoritma 2

Waktu 1 hari 1 hari

n 35 31500

• Efficiency algoritma lebih baik dari efficiency hardware.

Performance of Program • Performansi program adalah besar memory komputer dan banyaknya waktu yang dibutuhkan untuk menjalankan sebuah program. • Ukuran performansi sebuah program ditentukan oleh dua faktor : 1. Space complexity 2. Time complexity

Space & Time complexity • Space complexity adalah besar memory yang dibutuhkan untuk menjalankan program. • Time complexity adalah banyaknya waktu yang dibutuhkan untuk menjalankan program.

Space complexity • Faktor-faktor yang mempengaruhi space complexity : 1. Instruction space space yang dibutuhkan untuk menyimpan hasil compile dari program. 2. Data space space yang dibutuhkan untuk menyimpan semua variabel maupun konstanta. 3. Environment stack space space yang dibutuhkan untuk menyimpan informasi dari eksekusi yang tertunda.

Time complexity • Perhitungannya didapatkan dari seluruh faktor yang ada pada space complexity dan operasi/perintah yang ada pada program. • Sangat dipengaruhi oleh algoritma program.

Time Complexity • Dibedakan menjadi 3 macam : 1. Tmax(n) => worst case 2. Tmin(n) => best case 3. Tavg(n) => average case

Kompleksitas Waktu Aturan penghitungan kompleksitas waktu T(n) : a. Pengisian nilai(assignment), perbandingan, operasi aritmatik, read, write : membutuhkan waktu 1 b. Pengaksesan array, memilih field dari sebuah record : waktu 1. c. If C then S1 else s2, membutuhkan waktu Tc + max(Ts1, Ts2) yang dalam hal ini Tc, Ts1, dan Ts2 adalah kompleksitas waktu C, S1, dan S2. d.Perulangan for, kompleksitas waktunya adalah jumlah perulangan dikali dengan kompleksitas waktu dari body perulangan. e. While C do S atau repeat S until C. Untuk kedua perulangan tersebut kompleksitas waktu yang dibutuhkan adalah jumlah perulangan dikali dengan kompleksitas waktu dari body C dan S. f. Prosedur dan fungsi. Waktu yang dibutuhkan untuk memindahkan kendali dari fungsi yang dipanggil adalah 1.

Contoh Perhitungan T(n) Perhatikan sintax berikut : Public static Computable(....) { if(a.length==0) return null; a[0]=0; for(int i=0;i
Untuk worst case didapatkan : T(n) = 2n+4

0 0 1 1 n+1 n 1

Untuk best case didapatkan : T(n) = 5

0 0 1 1 1 1 1

Untuk average case didapatkan dari rata-rata T(n) worst dan best case : T(n) = (2n+4+5)/2 => T(n) = n+9/2

Latihan 1. Dari program berikut tentukan T(n) worst, best dan average case.

Public static void main(...) { for(int i=0;i
Penyederhanaan Persamaan T(n) • Misal worst case dari sebuah algoritma adalah T(n) = 2n2 + 6n + 1. persamaan ini dapat disederhanakan dengan 2n2 • Perhatikan tabel berikut : T(n) = 2n2 + 6n + 1

2n2

10

261

200

100

2061

2000

1000

2.006.001

2.000.000

10000

2.000.060.001

2.000.000.000

n

• Untuk n bernilai besar, bisa dikatakan bahwa = 2n2 + 6n + 1 sebanding dengan 2n2 , sehingga : T(n) = 2n2

Big-O • Pada kompleksitas waktu asimptotik, kinerja algoritma diukur dengan membuat makna “sebanding”. Yaitu dengan menghilangkan faktor koefisien dalam ekspresi T(n). • Big-O digunakan persamaan dari T(n).

untuk

menyederhanakan

Notasi Big-O Notasi O disebut notasi Big-O yang merupakan notasi untuk kompleksitas waktu asimptotik. Dituliskan : O(f(n)). Cara penyederhanaan : Jika kompleksitas waktu T(n) dari algoritma diketahui, maka kompleksitas waktu asimptotik dapat langsung ditentukan denganmengambil suku yang mendominasi fungsi T dan menghilangkan koefisien-nya. Contoh : T(n) = n-1 , T(n)=(n+1)/2 ,

maka : T(n)= O(n) maka : T(n)=O(n)

Aturan Koefisien Big-O • T(n) = O(f(n)) dibaca Tn adalah O dari f(n) • Jika pada persamaan big-O memiliki koefisien, maka T(n) <= O(C[f(n)]). Untuk memenuhi aturan tersebut yang perlu dilakukan adalah menemukan pasangan C dan n0 sehingga memenuhi aturan:

T(n) <= C(f(n))

Penjelasan • Suku-suku yang tidak mendominasi pada T(n) dapat diabaikan, sehingga kompleksitas waktu untuk T(n) adalah : 2 n2 + suku-suku lainnya. • Dengan mengabaikan suku-suku yang lain yang tidak mendominasi pada 2 n2 maka :

T(n) = O(2 n2)

[dibaca : T(n) adalah O dari 2n2]

• Jadi kita telah mengganti ekspresi T(n) = 2n2 + 6n + 1 dengan yang lebih sederhana seperti 2n2.

Contoh • Jadi untuk T(n) = 2n2 + 6n + 1 jika disederhanakan dengan menggunakan aturan big-O harus memenuhi aturan T(n)<=C(f(n)). • Sehingga penyederhanaannya sbb : Untuk C(f(n)) = 9n2 koefisien (c) =9, n0 =1 (memenuhi) Untuk C(f(n)) = 2n2 koefisien (c) =2, n0 =1 (Tidak memenuhi aturan big-O karena T(n) > c(f(n)) ).

Latihan Tentukan Big-O dari T(n). Kemudian tunjukan bahwa T(n) <=C(f(n)) untuk pasangan C dan n0 yang sesuai: 1. 2. 3. 4. 5.

T(n) = 3n +2 T(n) = 6n3+12n2+1 T(n) = 10n2+4n+2 T(n) = 6n3+12n2+1 T(n) = 10n2+4n+2

Latihan 1. T(n) = n2/10+2n = O(2n) 2. T(n) = 6n2 + 2n = O(2n) 3. T(n) = 3n2+2n+5 = O(n2)

Latihan 1. Dari program berikut tentukan T(n). 2. Dari T(n) yang telah didapatkan tentukan big-O. 3. Kemudian tentukan pasangan C dan n yg mungkin. Public static void main(...) { for(int i=0;i
Teorema Big-O • Misal T1(n) = O(f(n)) dan T2(n) = O(g(n)), maka : 1. T1(n) + T2(n) = O(f(n)) + O(g(n)) = O(max(f(n),g(n))) 2. T1(n)T2(n) = O(f(n))O(g(n)) = O(f(n)g(n)) 3. O(cf(n)) = O(f(n)), c adalah tetapan 4. f(n) = O(f(n))

Pengelompokan Algoritma (Berdasarkan Notasi Big-O) Constant

O(1)

Logarithmic

O(log n)

Linear

O(n)

Quadratic

O(n2)

Cubic

O(n3)

Polynomial

O(np)

Exponential

O(an)

Notasi Big-Omega dan Big-Tetha • Big-Ω (Big-Omega) Digunakan untuk mendefinisikan batas bawah (lower bound) dalam kompleksitas waktu. T(n) = Ω (g(n))(dibaca T(n) adalah Omega dari f(n)) T(n) berorde paling kecil g(N) bila terdapat koefisien C dan no sedemikian sehingga : T(n) ≥ C(f(n)) untuk n ≥ no

• Big-Θ (Big-Tetha) T(n) = Θ (h(n)) (dibaca T(n) adalah tetha dari h(n)) T(n) berorde sama dengan h(n) jika T(n)=O(h(n)) dan T(n)= Ω(g(n))

Contoh • Tentukan notasi Ω dan Θ untuk T(n) = 2n2+6n+1. jawab :  2n2+6n+1 ≤ 9n2 n ≥ 1 (C=9) maka : 2n2+6n+1 =O(n2 ) 2n2+6n+1 ≥ 2n2 n ≥ 1 (C=2) maka : 2n2+6n+1 =Ω(n2 ) Karena 2n2+6n+1 =O(n2 ) dan 2n2+6n+1 =Ω(n2 ), maka 2n2+6n+1 =Θ(n2 )

Pustaka • Sartaj Sahni , “Data Structures & Algorithms”, Presentation L20-24. • Mitchell Waite, “Data Structures & Algorithms in Java”, SAMS, 2001

Algoritma dan Struktur Data. Performansi Algoritma

Recommend Documents