Efektif, Efisien, Simplicity, dan Big-O dalam algoritma

Informatika, Pemrograman

1. Efektif

Algoritma dikatakan efektif jika algoritma tersebut menghasilkan suatu solusi yang sesuai dengan masalah yang diselesaikan. Dalam arti lain algoritma tersebut harus tepat guna. Selain itu, semua instruksi harus bisa dikerjakan oleh pemroses yang akan menjalankannya.

Contoh kasus :
Hitung 21/3 dengan presisi sempurna

Instruksi diatas tidak efektif. Agar efektif, harus diubah menjadi “Hitung 21/3 dengan toleransi sampai 5 digit dibelakang koma”

2. Efisien

Algoritma dikatakan efisien jika waktu proses suatu algoritma relatif lebih singkat dan penggunaan memori komputernya lebih sedikit.

Contoh kasus:
Hitung 275 + 25

Algoritma dapat dikatakan efisien jika langsung melakukan penjumlahan 275 + 25 = 300 daripada
275.0 + 25.0 = 0.275*103 + 0.25*102
= 0.275*103 + 0.025*103
= (0.275+ 0.025)*103
= 0.3*103
= 300.0

Hal ini karena persamaan 275 + 25 = 300 memberikan waktu proses lebih singkat daripada persamaan 275.0 + 25.0 = 0.275*103 + 0.25*102 yang merubah tipe data terlebih dahulu dari bilangan bulat ke bilangan riil.

3. Simplicity

Maksud Simplicity adalah barisan instruksi harus dalam urutan yang sederhana dan berhingga agar masalah yang dapat terselesaikan dalam waktu yang masuk akal. Simplicity berhubungan erat dengan keefektifan dan efisiensi. Suatu algoritma dapat dikatakan simple jika algoritma itu efektif dan efisien.

4. Big-O

Big-O adalah notasi yang mengukur kompleksitas algoritma yang terdiri dari penggunaan sumber daya, seperti waktu eksekusi atau pemakaian memori, dalam hal ukuran sebuah input.

Dengan memakai Big-O kita bisa membahasakan berapa lama sebuah algoritma membutuhkan waktu dan alokasi memori sehingga kita bisa membandingkan algoritma mana yang lebih efisien dalam menyelesaikan suatu masalah.

Contoh penggunaan Big-O sebagai alat ukur waktu eksekusi:

a. Waktu konstan

def print_item_pertama(list):
    print list[0]

Fungsi diatas berjalan dalam satuan waktu: O(1) atau waktu konstan terhadap input nya yaitu: list. Jumlah item dalam list bisa saja berisi sebuah item atau 10000 item, namun dalam eksekusinya hanya membutuhkan 1 langkah yaitu: print list[0]

b. Waktu linear

def print_semua_item(list):
    for item in list:
        print item

Fungsi diatas berjalan dalam satuan waktu: O(n) atau waktu linear. n adalah jumlah item dalam list. Jika list memiliki 100 item, fungsi tersebut akan mencetak sebanyak 100 kali. Jika memiliki 10000 item, fungsi tersebut akan mencetak sebanyak 10000 kali. Jumlah eksekusi print item linear dengan jumlah item dalam “list”

c. Waktu quadratic

def print_semua_titik(list_titik):
    for koordinat_x in list_titik:
        for koordinat_y in koordinat_x:
            print koordinat_x, koordinat_y

Fungsi diatas memiliki 2 loop yang bentuknya adalah loop didalam loop atau istilah pemrogramannya nesting loop. Jika jumlah item dalam list_titik adalah n, maka:

  • loop dalam baris ke #2 akan berjalan sebanyak n kali dan
  • loop dalam baris ke #3 akan berjalan sebanyak n kali untuk setiap n kali loop dalam baris ke #2

Sehingga fungsi tersebut berjalan dalam satuan waktu: O(n^2) atau waktu quadratic (lihat pangkat 2 dalam n). Jika dalam list_titik terdapat 100 item, fungsi akan mencetak sebanyak 10000 kali.

Contoh penggunaan Big-O sebagai alat ukur alokasi memori:

a. Ruang memori konstan

def say_hi_n_times(n):
  for time in xrange(n):
    print "hi"

Fungsi diatas menggunakan ruang memori: O(1) atau ruang memori konstan. Jumlah variabel yang dipakai pada baris ke #3 adalah tetap: time. Nilai didalam variabelnya mungkin berubah, namun jumlah variabelnya tidak berubah.

b. Ruang memori linear

def list_of_hi_n_times(n):
  hi_list = []
  for time in xrange(n):
      hi_list.append("hi")
  return hi_list

Fungsi diatas menggunakan ruang memori: O(n) atau ruang memori linear.

Jumlah variabel yang dipakai pada baris ke #2 (hi_list) akan berubah tergantung dengan nilai n. Semakin bertambah jumlah n, semakin bertambah juga ruang memori yang dipakai untuk variabel hi_list.

Sebagai alat ukur alokasi memori, Big-O dipakai untuk mengukur penambahan jumlah ruang memori. Perhitungan jumlah input tidak termasuk disini. Sebagai contoh fungsi berikut memakai ruang memori konstan walaupun jumlah input-nya adalah n.

def get_largest_item(items):
  largest = float('-inf')
  for item in items:
    if item > largest:
      largest = item
  return largest

Referensi :

  • Makalah EMA_belajar memprogram_STMIK AMIKOM Yogyakarta.pdf (diperoleh dari google.com)
  • Pemrograman – wikipedia
  • Interview cake

Bacaan Tambahan :

Satu pemikiran pada “Efektif, Efisien, Simplicity, dan Big-O dalam algoritma

Tinggalkan Balasan

Alamat email Anda tidak akan dipublikasikan. Ruas yang wajib ditandai *