Pertemuan 3 : Algoritma dan fungsi kompleksitas


Waktu proses algoritma

Tidak semua algoritma dapat selesai diproses dalam waktu kurang dari satu detik. Algoritma yang kompleks dapat memerlukan waktu beberapa menit hingga berhari-hari untuk menyelesaikan prosesnya.

Proses algoritma tidak dinyatakan dengan satuan ms (milisecond) tetapi dengan satuan ek (jumlah eksekusi). Why?

karena kecepatan tiap komputer pasti berbeda-beda.

Contoh sederhana :

20131015_141559

20131015_141629

20131015_143934

Variasi Waktu Proses

Algoritma bekerja berdasarkan input yang dimasukkan oleh user. Input memiliki ukuran. Makin besar ukuran input yang dimasukkan, pada umumnya waktu proses akan semakin lama.

Tergantung pada isi input, waktu proses dapat bervariasi :

  • Keadaan terbaik (best case)

Dilambangkan dengan notasi Omega.

–Keadaan rata-rata (average case)

Dilambangkan dengan notasi Theta.

–Keadaan terburuk (worst case)

Dilambangkan dengan notasi O(…) dibaca Big-O.

*Kinerja sebuah algoritma biasanya diukur dengan (worst case) yang dinyatakan dengan Big-O.

20131015_160646

•Contoh : Pseudocode Selection Sort (pseudocode 3.6)

1 for i=1 to N-1 do

2   min=i

3   for j=i+1 to N do

4     if A[j]<A[min] then

5       min=j

6     end if

7   end for

8   swap(A[i],A[min])

9 end for

•Hitung waktu proses algoritma yang diperlukan untuk mengurutkan deretan yang berisi 8 angka acak !

•Bagaimana jika ukuran input belum diketahui?

–Dinyatakan dengan N

–Waktu proses dinyatakan dengan sebuah persamaan N, selanjutnya disebut Fungsi Kompleksitas

•Fungsi Kompleksitas menyatakan seberapa kompleksnya sebuah algoritma.

sumber :[buku utama, bab 3.2]

nama buku : Algoritma itu mudah

Penulis : Robert Setiadi

Penerbit : PT Prima Infosarana Media

Jawab :

•Asumsi bahwa nilai N belum diketahui

•Bisa dihitung bahwa untuk setiap perulangan i akan terjadi perulangan j sebanyak N-1, N-2, N-3, …, 1 kali

•Misalkan nilai N adalah 5, berarti kita perlu menghitung 5+4+3+2+1 (rumus deret hitung).

DN = N/2 (2a + (n-1)b) 

N= panjang deret, a = nilai suku pertama, b = nilai perbedaan antar suku. 

Dalam kasus ini, adan b adalah 1, maka rumus di atas jika diperbaiki menjadi :

DN = N(N+1) / 2. 

•Dengan rumus Fungsi Kompleksitas N(N+1)/2 berarti jika N=5 maka waktu proses adalah 15.

•Jika nilai N diperbesar menjadi 8, maka waktu proses menjadi 36.

•Nilai N dan waktu proses bisa dipetakan dalam sebuah koordinat Cartesius dengan N di sumbu x dan waktu proses di sumbu y.

Terlihat bahwa waktu proses algoritma Selection Sort bertumbuh (growth rate) secara linear.

•Fungsi Kompleksitas algoritma Selection Sort di atas : f(n) = n(n+1) / 2.

Advertisements

2 thoughts on “Pertemuan 3 : Algoritma dan fungsi kompleksitas

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s