algoritma dan pemrograman iii

ALGORITMA DAN PEMROGRAMAN III

Analisa Algoritma Algoritma Greedy Exploring Graph Algoritma Probabilistic

MATERI

Kuliah 50%◦ Tugas 20%◦ UTS 30%◦ UAS 50%

Praktikum 50%

PENILAIAN

Algoritma membantu kita memahami skalabilitas program kita

Analisa algoritma memberi gambaran informasi tentang ‘perilaku program’ kita

Mempelajari bagaimana menerapkan algoritma yang baik untuk kasus tertentu membedakan profesi system analyst dan programmer

ANALISA ALGORITMA

Apa yang membuat sebuah algoritma dikatakan LEBIH BAIK dari algoritma yang lain? Kompleksitas waktu (Time Complexity) Kompleksitas ruang (Space Complexity)Kecenderungan saat ini: ruang (hard disk) semakin murah kapasitas data yang diproses semakin besar waktu pemrosesan harus semakin cepat

Kompleksitas waktu menjadi variabel yang sangat penting

Prinsip Perbandingan Algoritma

Efisiensi suatu algoritma tidak dapat diukur dengan satuan waktu (detik, milidetik dsb), karena waktu tempuh algoritma sangat tergantung pada :◦ Banyaknya data◦ Spesifikasi komputer Hardware◦ Compiler software◦ Tegangan listrik◦ Lain-lain

Ukuran Efisiensi Waktu

Efisiensi waktu dalam algoritma diukur dengan satuan n (problem size)

4 langkah untuk menentukan ukuran efisiensi waktu antara lain :◦ Menentukan problem size (n)◦ Menentukan operasi dominan◦ Menentukan fungsi langkah g(n)◦ Menentukan kompleksitas waktu O(f(n)) Big Oh

Efisiensi Waktu

Problem size

Operasi dominan merupakan operasi yang paling banyak dilakukan untuk memecahkan suatu permasalahan.

Operasi dominan ini sangat tergantung pada permasalahan dan operasi yang dilakukan yang banyaknya tergantung pada n

Menentukan Operasi Dominan

Pada algoritma menentukan max/min operasi dominannya adalah operasi perbandingan “<“ atau “>”

Pda algoritma searching operasi dominannya adalah operasi “=“

Contoh

g(n) = banyak kali operasi dominan dilakukan dalam (n)

Menentukan fungsi langkah g(n)

Suatu algoritma dengan fungsi langkah g(n) dikatakan mempunyai kompleksitas waktu O(f(n)) jika terdapat konstanta c>0 sedemikian hingga : g(n) ≤ c.f(n) untuk n > n0

◦ Algoritma MaxMin g(n)= 2n-2 O(n)◦ Algoritma Bubblesort g(n) = n2/2-n/2 O(n2)

Menentukan kompleksitas waktu O(f(n))

Faktor-faktor yang menentukan banyak langkah antara lain :1. Banyaknya operator dasar yang digunakan2. Assigment (konstanta c)3. Function Call4. Struktur Program

- Sekuensial- Percabangan- Kalang (loop)

Efisiensi Algoritma

Misalkan dalam algoritma terdapat blok statement, masing-masing mempunyai banyak langkah :S1 banyak langkah P1S2 banyak langkah P2S3 banyak langkah P3Sn banyak langkah Pn

Total banyak langkah blok-blok statement tersebut adalah

SEKUENSIAL

x x * y operasi 1 = 1 y a * sin(x) operasi 1, procedure 1 = 2 Readln(b) assigment 1 = 1 Writeln (x+y+b) assigment 1

operasi 2 = 3

Banyak langkah = 7

Contoh Sekuensial

Hitung banyak langkah dari algoritma berikut :read(panjang)read(lebar)luas panjang * lebarkeliling 2 * (panjang + lebar)write(luas)write(keliling)

Soal

Bentuk IF k THEN S1ELSE S2

k = kondisi dengan banyak langkah cS1 , S2 = blok statement dengan banyak langkah P1,P2

Percabangan

Kasus terbaik mempunyai banyak langkahc + min (P1, P2)

Kasus terburuk mempunyai banyak langkahc + max (P1, P2)

Operator dasar logika : AND, OR, NOT dihitung 1 langkah

Percabangan

Percabangan

C = 1P1 = 2P2 = 1Kasus terburuk = c + max (P1, P2) = 1 + max(2,1) = 3

Yang dianalisa hanya For Loop

Bentuk umumFor variable nilai awal To nilai akhir Step S

Perulangan (Loop)

Kasus IStatement S mempunyai banyak langkah yang tidak tergantung nilai counterFor counter : awal To akhir

S

Counter ≤ Akhir S dieksekusi sebanyak akhir – awal + 2 kali

Counter = counter + 1 S dieksekusi sebanyak akhir – awal + 1

kali

Perulangan (Loop)

Banyak Langkah = (akhir – awal + 2) + (akhir – awal + 1) (p + 1)

Contoh :For i = 1 to n

x : = x + 5y : = y + x

Perulangan (Loop)

Kasus IIBanyak langkah S bergantung nilai CounterContoh :For i := 1 To n

x := x + yFor j := i To n

y := i + j

Perulangan (Loop)