2013-12-06 Tutoring Kalkulus II di SAC-BINUS di Ruang 804 di kampus Anggrek

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.

4 thoughts on “Pertemuan 3 : Algoritma dan fungsi kompleksitas

  1. Hello Web Admin, I noticed that your On-Page SEO is is missing a few factors, for one you do not use all three H tags in your post, also I notice that you are not using bold or italics properly in your SEO optimization. On-Page SEO means more now than ever since the new Google update: Panda. No longer are backlinks and simply pinging or sending out a RSS feed the key to getting Google PageRank or Alexa Rankings, You now NEED On-Page SEO. So what is good On-Page SEO?First your keyword must appear in the title.Then it must appear in the URL.You have to optimize your keyword and make sure that it has a nice keyword density of 3-5% in your article with relevant LSI (Latent Semantic Indexing). Then you should spread all H1,H2,H3 tags in your article.Your Keyword should appear in your first paragraph and in the last sentence of the page. You should have relevant usage of Bold and italics of your keyword.There should be one internal link to a page on your blog and you should have one image with an alt tag that has your keyword….wait there’s even more Now what if i told you there was a simple WordPress plugin that does all the On-Page SEO, and automatically for you? That’s right AUTOMATICALLY, just watch this 4minute video for more information at. Seo Plugin

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