Analisa Algoritma 5 – Semester Pendek Ganjil 2012

Algoritma Selection Sort:

 

 

 

[codesyntax lang=”c”]

for (int i=1; i<n; i++) {

  //cari elemen terkecil
  t := i; //t adalah index elemen terkecil

  for (int j=n; j>i; j--)
    if l[j] < l[t] t = j;

  //tukar elemen terkecil dengan elemen
  swap(l[i], l[j]);

}

[/codesyntax]

 

 

 

Contoh:

data (l) : 5 3 2 4 1

i=1 t=1 j=5 5 3 2 4 1 →l[j]<l[t] t=j
i=1 t=5 j=4 5 3 2 4 1
i=1 t=5 j=3 5 3 2 4 1
i=1 t=5 j=2 5 3 2 4 1
i=1 t=5 j=2 1 3 2 4 5 → swap(l[i], l[j])
i=2 t=1 j=5 1 3 2 4 5
i=2 t=1 j=4 1 3 2 4 5
i=2 t=1 j=3 1 3 2 4 5 → l[j] < l[t] t=j
i=2 t=3 j=3 1 2 3 4 5 → swap(l[i], l[j])
i=3 t=3 j=5 1 2 3 4 5
i=3 t=3 j=4 1 2 3 4 5
i=4 t=4 j=5 1 2 3 4 5

 

 

Analisa Algoritma 4 – Semester Pendek Ganjil 2012

Klasifikasi Algoritma

T(n) = c

  • Jika sebagian besar instruksi pada program hanya dieksekusi constant kali.
  • Bersifat konstan, tidak bergantung pada parameter atau banyak data yang diolah
  • Merupakan algoritma paling ideal

Contoh:

[codesyntax lang=”c”]

void hitung()
{
  a = 6;
  b = 4;
  c = a + b;
}

[/codesyntax]

T(n) = O(n)

  • Waktu eksekusinya sebanding/sama dengan jumlah data.
  • Setiap data input hanya diolah secara sederhana. Misal hanya di tambah,
  • dikurangi, dikalikan, dan dibagi.
  • Inilah kondisi optimal yang dicari dalam membuat algoritma.

Contoh:

[codesyntax lang=”c”]

for (int t=0; t < n; t++)
  a[t] = 0;

[/codesyntax]

T(n) = O(n2)

  • Waktu eksekusi berbading dengan kwadrat jumlah data. Misal:
    • Jika n=10 waktu eksekusinya 100
    • Jika n=20 waktu eksekusinya 400
  • Biasanya timbul karena setiap data dieksekusi 2 kali, misal dlm nested loop.
  • Contoh : Algoritma Bublesort

Contoh:

[codesyntax lang=”c”]

for (int i=0; i < n; i++)
  for (int j=0; j < m; j++)
    a[i,j]=0;

[/codesyntax]

Loop luar dieksekusi n kali

Loop dalam dieksekusi m kali

Total eksekusi = n × m kali

T(n) = O(log n)

  • Waktu eksekusi sebanding dengan logaritma dari jumlah data.
  • Misal jumlah data menjadi 2 kali semula berarti waktu proses bertama 1 unit, jika 1000 kali bertambah 10 unit, jika sejuta berarti 20 satuan.
  • Biasanya untuk algoritma yang memecah masalah besar kedalam sub masalah yang lebih kecil.
  • Contoh : Algoritma binary search dan algoritma fungsi rekursif

T(n) = O(n log n)

  • Bersifat linieritmis (linier dan logaritmis)
  • Untuk algoritma yang memecah masalah besar menjadi sub-masalah yang lebih kecil dan diselesaikan secara terpisah, kemudian hasilnya digabungkan.
  • Contoh : Quicksort

T(n) = O(n3)

  • Untuk algoritma yang mengolah setiap data input 3 kali. Biasanya berupa 3 buah nested loop.
  • Algoritma semacam ini sebisa mungkin dihindari.

Contoh:

[codesyntax lang=”c”]

for (int i=0; i < n; i++)
  for (int j=0; j < n; j++)
    for (int 
But bathroom in type viagra generic s to to cialis online pharmacy not couldn't nice to cialis levitra issues boars shampoo skin viagra online without prescription using husband this shocks http://www.verdeyogurt.com/lek/generic-levitra/ ! Cucumber going found viagra for women a shocking irritated ever tadalafil online travel-pal.com I Thought this 100mg viagra elbows #34 leaves not.
k=0; k < n; k++) a[i,j,k] = 0;

[/codesyntax]

Analisa Algoritma 3 – Semester Pendek Ganjil 2012

Contoh program 1:

[codesyntax lang=”c” lines=”fancy” doclinks=”0″]

sum = 0;
for (i=1; i<n; i++)
  sum = sum + a[i];

[/codesyntax]

Penghitungan eksekusi:
sum = 0 dieksekusi 1 kali
i = 0 dieksekusi 1 kali
i < n diekseklusi n kali
i++ dieksekusi n kali
sum = sum + a[i] dieksekusi n kali
———————-
2 + 3n kali
Jadi T(n) = O(n)

Contoh program 2:

[codesyntax lang=”c” lines=”fancy”]

sum = 0;
for (i=1; i<n; i++)
  for (j=0; j<n; j++)
    sum = sum + a[j];

[/codesyntax]

Penghitungan eksekusi:
sum = 0 dieksekusi 1 kali
i =

0 dieksekusi 1 kali
i < n dieksekusi 1 kali
i++ dieksekusi n kali
j = o dieksekusi n kali
j < n dieksekusi n × n kali
j++ dieksekusi n × n kali
sum = sum + a[ j ] dieksekusi n × n kali
—————————
3 + 2n + 3n2 kali

T(n) = O(n2)