7. Kompleksitas Algoritma


Sebuah algoritma tidak saja harus benar (sesuai spesifikasi persoalan), tetapi juga harus mangkus (efisien). Algoritma yang bagus adalah algoritma yang mangkus (efisien). Kemangkusan algoritma diukur dari waktu (time) yang diperlukan untuk menjalankan algoritma dan ruang (space) memori yang dibutuhkan oleh algoritma tersebut. Algoritma yang mangkus ialah algoritma yang meminimumkan kebutuhan waktu dan ruang memori. 

Kebutuhan waktu dan ruang suatu algoritma bergantung pada ukuran masukan (n) yang menyatakan ukuran data yang diproses oleh algoritma. Kemangkusan/ keefisienan algoritma dapat digunakan untuk menilai algoritma yang bagus dari sejumlah penyelesaian persoalan, sebab sebuah persoalan dapat memiliki banyak algoritma penyelesaian, contoh: persoalan pengurutan (sort), ada puluhan algoritma pengurutan (selection sort, insertion sort, bubble sort, dll).

Mengapa kita memerlukan algoritma yang mangkus? lihat grafik berikut:

Contoh kasus: Sebuah persoalan diselesaikan dengan algoritma yang waktu komputasinya dalam orde eksponensial 2n, lalu algoritma tersebut kita jalankan pada program komputer dengan kecepatan prosesornya 10-4, seperti grafik diatas.

Model perhitungan kebutuhan waktu 

Menghitung kebutuhan waktu algoritma dengan mengulur waktu eksekusi riilnya (dalam satuan detik) ketika program (yang merepresentasikan sebuah algoritma) dijalankan oleh komputer bukanlah cara yang tepat. Karena:
1. Setiap komputer dengan arsitektur berbeda memiliki bahasa mesin yang berbeda sehingga waktu setiap operasi antara satu komputer dengan komputer lain tidak sama.
2. Compiler bahasa pemrograman yang berbeda menghasilkan kode bahasa mesin yang berbeda sehingga waktu setiap operasi antara compiler dengan compiler lain tidak sama.
  • Kompleksitas waktu, t(n) diukur dari jumlah tahapan komputasi yang dilakukan di dalam algoritma sebagai fungsi dari ukuran masukan n.
  • Kompleksitas ruang, S(n) diukur dari memori yang digunakan oleh struktur data yang terdapat di dalam algoritma sebagai fungsi dari ukuran masukan n.
  • Dengan menggunakan besaran kompleksitas waktu/ ruang algoritma kita dapat menentukan laju peningkatan waktu (ruang) yang diperlukan algoritma dengan mengingkatnya ukuran masukan n.
Sehingga dalam pembahasan kali ini hanya membatasi bahasan kompleksitas waktu saja karena:
  • Materi struktur data diluar lingkup mata kuliah matematika diskrit dan 
  • Saat ini memori komputer bukan persoalan yang kritis dibandingkan waktu.
Ukuran masukan (n) menyatakan banyaknya data yang diproses oleh sebuah algoritma.


Contoh:
  1. Algoritma pengurutan 10 elemen larik (array), maka n=10.
  2. Algoritma pencarian pada 500 elemen larik, maka n=500
  3. Algoritma TSP pada sebuah graf lengkap dengan 100 simpul, maka n=100
  4. Algoritma perkalian 2 buah matriks berukuran 50x50, maka n=50
  5. Algoritma menghitung polinom dengan derajat <= 100, maka n= 100
Dalam perhitungan kompleksitas waktu, ukuran masukan dinyatakan sebagai variabel n saja (bukan instans suatu nilai).

  • Pekerjaan utama di dalam kompleksitas waktu adalah menghitung (counting) jumlah tahapan komputasi didalam algoritma.
  • Jumlah tahapan komputasi dihitung dari beberapa kali suatu operasi dilakukan sebagai fungsi ukuran masukan (n)
  • Didalam sebuah algoritma terdapat banyak jenis operasi:
    • Operasi baca/ tulis, contoh: (input a, print a)
    • Operasi aritmetika (+, -, ", /), contoh: (a+b, M*N)
    • Operasi pengisian nilai (assignment), contoh (a -->10)
    • Operasi perbandingan, contoh  (a<b, k>=10)
    • Operasi pengaksesan elemen larik, pemanggilan prosedur/ fungsi dll
  • Untuk menyederhanakan perhitungan, kita tidak menghitung semua jenis operasi tetapi kita hanya menghitung jumlah operasi (tipikal) yang mendasari suatu algoritma.
Contoh operasi khas di dalam algoritma

1. Algoritma pencarian (searching)
    Operasi khas: operasi perbandingan elemen larik


2. Algoritma pengurutan (sorting)
   Operasi khas: operasi perbandingan elemen dan operasi pertukaran elemen.
3. Algoritma perkalian dua buah matriks AB=C
   Operasi khas: operasi perkalian dan penjumlahan


4. Algoritma menghitung nilai sebuah polinom p(x)=a0+a1x+a2x2+...+anxn
   Operasi khas: operasi perkalian dan penjumlahan

Contoh 1. Tinjau algoritma menghitung rerata elemen didalam sebuah larik (array).


Operasi yang mendasar pada algoritma tersebut adalah operasi penjumlahan elemen-elemen larik (yaitu sum <---sum+a[i]) yang dilakukan sebanyak n kali
Kompleksitas waktu: T(n)=n



















































Comments

Post a Comment