5302414047 algorithmic efficiency

1 Algorithmic Efficiency

Aulia Yuniar Sulistyo

EFISIENSI ALGORITMA

Pertama, penjelasan tentang algoritma itu sendiri.

Algoritma merupakan suatu langkah kerja/ uruta langkah kerja yang logis dan tepat

untuk memecahkan suatu masalah, atau dalam ilmu komputer algoritma merupakan

suatu konsep dasar dari sebuah program yang dimana dalam pembuatannya di perlukan

daya nalar dan pikir yang baik maupun logis.

Jenis Algoritma

Terdapat beragam klasifikasi algoritma dan setiap klasifikasi mempunyai alasan

tersendiri. Salah satu cara untuk melakukan klasifikasi jenis-jenis algoritma adalah

dengan memperhatikan paradigma dan metode yang digunakan untuk mendesain

algoritma tersebut. Beberapa paradigma yang digunakan dalam menyusun suatu

algoritma akan dipaparkan dibagian ini. Masing-masing paradigma dapat digunakan

dalam banyak algoritma yang berbeda.

Berikut ini adalah beberapa rumpun algoritma yang terkenal, yaitu:

Metode Greedy.

Dynamic Programming.

Kompresi data.

Backtracking.

Branch and Bound.

Divide and Conquer

Masing-masing algoritma diatas memiliki keunggulan dan tentunya juga memiliki

kelemahan.

Divide and Conquer yaitu paradigma untuk membagi suatu permasalahan besar

menjadi permasalahan-permasalahan yang lebih kecil. Pembagian masalah ini

dilakukan terus menerus sampai ditemukan bagian masalah kecil yang mudah untuk

dipecahkan. Singkatnya menyelesaikan keseluruhan masalah dengan membagi masalah

besar dan kemudian memecahkan permasalahan-permasalahan kecil yang terbentuk.

Dynamic programming adalah paradigma pemrograman dinamik akan sesuai jika

digunakan pada suatu masalah yang mengandung sub-struktur yang optimal (, dan

mengandung beberapa bagian permasalahan yang tumpang tindih . Paradigma ini

sekilas terlihat mirip dengan paradigma Divide and Conquer, sama-sama mencoba

untuk membagi permasalahan menjadi sub permasalahan yang lebih kecil, tapi secara

intrinsik ada perbedaan dari karakter permasalahan yang dihadapi.

Metode greedy merupakan sebuah algoritma serakah mirip dengan sebuah

Pemrograman dinamik, bedanya jawaban dari submasalah tidak perlu diketahui dalam

setiap tahap; dan menggunakan pilihan "serakah" apa yang dilihat terbaik pada saat itu.



Kompresi Data adalah sebuah cara untuk memadatakan data sehingga hanya

memerlukan ruangan penyimpanan lebih kecil sehingga lebih efisien dalam

menyimpannya atau mempersingkat waktu pertukaran data tersebut.

Backtracking merupakan perbaikan dari pendekatan kekerasan, yang secara sistematis

mencari solusi untuk masalah di antara semua pilihan yang tersedia.

Branch and Bround (B&B) juga merupakan metode pencarian di dalam ruang solusi

secara sistematis. Branch and Bround digunakan untuk mencari solusi optimal dari

berbagai optimasi masalah, terutama dalam diskrit dan optimasi kombinatorial. Ini

terdiri dari pencacahan sistematis semua solusi kandidat, dimana himpunan bagian besar

calon sia-sia dibuang secara massal, dengan menggunakan perkiraan batas bawah dan

atas kuantitas yang sedang dioptimalkan.

Kompleksitas Algoritma

Pada bagian sebelumnya kita telah mempelajari mengenai algoritma yang baik, serta

bagaimana membuktikan sebuah algoritma akan memberikan hasil yang benar. Selain

memberikan hasil yang benar, efisiensi dari waktu eksekusi ataupun penggunaan

memori dari algoritma adalah hal yang penting bagi sebuah algoritma. Bagian ini akan

membahas bagaimana mengukur efisiensi sebuah algoritma, sehingga kita dapat

memilih algoritma yang baik atau memperbaiki algoritma yang ada.Langsung saja, kita

mulai dengan sebuah contoh algoritma untuk menghitung perpangkatan dua bilangan.

Hasil akhir dari kode yang akan dikembangkan direpresentasikan oleh fungsi matematis

berikut:

F(x,y)=Xy

Salah satu implementasi sederhana untuk fungsi matematis di atas adalah:

def pangkat(x, y):

hasil = 1

for i in range(0, y):

hasil = x * hasil

return hasil

Pada dasarnya yang kita lakukan pada kode di atas ialah mengkalikan x dengan dirinya

sendiri sebanyak y kali, dan menyimpan hasil kali tersebut di dalam variabel hasil.

Baris hasil = x * hasil melakukan perkalian x dengan dirinya sendiri, dan perulangan

dilakukan untuk memastikan baris ini dijalankan sebanyak y kali.

Dengan asumsi bahwa algoritma perpangkatan yang kita tuliskan di atas sudah benar,

pertanyaan selanjutnya tentunya adalah: seberapa efisien kah algoritma tersebut?



Terdapat banyak cara untuk mengukur efisiensi sebuah algoritma, tentunya dengan

kelebihan dan kekurangan dari masing-masing cara tersebut. Mari kita lihat cara

mengukur efisiensi yang paling sederhana terlebih dahulu: melihat berapa langkah yang

perlu dijalankan untuk menyelesaikan algoritma tersebut. Jika kita memanggil

fungsi pangkatseperti berikut:

pangkat(2, 1)

Maka kode akan dieksekusi seperti berikut:

hasil = 1

for i in range(0, 1):

hasil = 2 * hasil

return hasil

yang kita perulangan for yang ada kita kembangkan akan menjadi:

hasil = 1

hasil = 2 * hasil

return hasil

Total terdapat tiga langkah yang perlu dijalankan untuk mendapatkan hasil pangkat yang

diinginkan. Sangat sederhana dan mudah. Bagaimana jika kita naikkan nilai

dari y sehingga kita memanggil pangkat(2, 2)?

Kode yang dieksekusi akan menjadi:

hasil = 1

for i in range(0, 2):

hasil = 2 * hasil

return hasil

yang ketika diuraikan menjadi:

hasil = 1

hasil = 2 * hasil

hasil = 2 * hasil

return hasil



dengan total 4 langkah eksekusi. Perhatikan bagaimana akibat dari meningkatkan

nilai y, jumlah eksekusi dari kode di dalam loop meningkat. Berdasarkan apa yang kita

dapatkan sejauh ini, kita dapat menyimpulkan bahwa jika dilakukan

pemanggilan pangkat(2, 5) maka kita akan mendapatkan hasil eksekusi:

hasil = 1

hasil = 2 * hasil

hasil = 2 * hasil

hasil = 2 * hasil

hasil = 2 * hasil

hasil = 2 * hasil

return hasil

dan seterusnya.

Notasi Asimtotik

Perhitungan pertumbuhan fungsi seperti yang kita lakukan sebelumnya sangat krusial

dalam menghitung efisiensi sebuah algoritma. Seperti layaknya hal-hal krusial lainnya

pada ilmu komputer, tentunya fungsi pertumbuhan ini juga memiliki notasi matematika

khusus. Penulisan fungsi pertumbuhan dilakukan dengan menggunakan notasi

asmtotik.

Terdapat beberapa jenis notasi asimtotik, tetapi kita hanya akan menggunakan dan

membahas satu notasi saja, yaitu notasi Big-O. Big-O dipilih karena merupakan notasi

yang paling populer dan paling banyak digunakan pada kalangan peneliti ilmu

komputer. Notasi Big-O digunakan untuk mengkategorikan algoritma ke dalam fungsi

yang menggambarkan batas atas (upper limit) dari pertumbuhan sebuah fungsi ketika

masukan dari fungsi tersebut bertambah banyak. Singkatnya, perhitungan jumlah

langkah dan pertumbuhannya yang kita lakukan pada bagian sebelumnya merupakan

langkah-langkah untuk mendapatkan fungsi Big-O dari sebuah algoritma.

Big-O, seperti namanya, dituliskan sebagai fungsi “O” dengan nilai masukan berupa

tingkat pertumbuhan dari fungsi yang dijabarkan. Misalnya, algoritma perpangkatan

dengan pertumbuhan linear yang kita kembangkan pada bagian sebelumnya memiliki

kelas Big-O O(n)

Karena berguna untuk mengkategorikan algoritma, terdapat beberapa jenis kelas

efisiensi umum yang dijumpai dalam Big-O, yaitu:



Fungsi Big-O Nama

O(1) Konstan

O(logn) Logaritmik

O(n) Linear

O(nlogn) n log n

O(n2) Kuadratik

O(nm) Polinomiale

O(n!) Faktorial

Apa guna dan penjelasan dari masing-masing kelas kompleksitas yang ada? Mari kita

lihat satu per satu.

Kriteria Efisiensi Umum

Bagian ini akan menjelaskan beberapa contoh kriteria kompleksitas algoritma yang

umum dijumpai, beserta dengan contoh kode algoritma yang memiliki kompleksitas

tersebut.

O(1): Kompleksitas Konstan

Sebuah algoritma yang memiliki kompleksitas konstan tidak bertumbuh berdasarkan

ukuran dari data atau masukan yang diterima algoritma tersebut. Bahkan, algoritma

dengan kompleksitas ini tidak akan bertumbuh sama sekali. Berapapun ukuran data atau

masukan yang diterima, algoritma dengan kompleksitas konstan akan memiliki jumlah

langkah yang sama untuk dieksekusi.

Karena sifatnya yang selalu memiliki jumlah langkah tetap, algoritma dengan

kompleksitas merupakan algoritma paling efisien dari seluruh kriteria yang ada. Contoh

dari algoritma yang memiliki kompleksitas konstan ialah algoritma yang digunakan

untuk menambahkan elemen baru ke dalam linked list. Contoh implementasi algoritma

ini pada bahasa Cadalah sebagai berikut:

void add_list(node *anchor, node *new_list)



{

new_list->next = anchor->next;

anchor->next = new_list;

}

Seperti yang dapat dilihat pada kode di atas, algoritma untuk menambahkan elemen baru

ke dalam linked list tidak memerlukan perulangan, percabangan, ataupun banyak

langkah. Untuk menambahkan elemen baru, kita cukup menjalankan dua langkah saja,

tidak peduli berapapun ukuran awal dari linked list yang ada. Dengan kata lain,

berapapun ukuran linked list awal, langkah untuk untuk menambahkan elemen baru

adalah konstan, yaitu dua langkah. Hal ini lah yang menyebabkan algoritma ini

dikatakan memiliki kompleksitas konstan.

Tingkat pertumbuhan dari algoritma dengan kompleksitas konstan dapat dilihat pada

gambar berikut:

Tingkat Pertumbunan Algoritma Kompleksitas Konstan

Algoritma Yang Efisien

Efisiensi algoritma dapat ditinjau dari 2 hal yaitu efisiensi waktu (seberapa cepat

algoritma dieksekusi) dan efisiensi memori (berapa banyak memori yang dibutuhkan

untuk menjalankan algoritma). Meskipun algoritma memberikan keluaran yang benar

(paling mendekati), tetapi jika kita harus menunggu berjam-jam untuk mendapatkan

keluarannya, algoritma tersebut biasanya tidak akan dipakai, setiap orang

menginginkan keluaran yang cepat. Begitu juga dengan memori, semakin besar

memori yang terpakai maka semakin buruklah algoritma tersebut. Dalam

kenyataannya, setiap orang bisa membuat algoritma yang berbeda untuk

menyelesaikan suatu permasalahan, walaupun terjadi perbedaan dalam menyusun



algoritma, tentunya kita mengharapkan keluaran yang sama. Jika terjadi demikian,

carilah algoritma yang paling efisien dan cepat.

>>> Faktor-faktor yang mempengaruhinya adalah :

– Banyak langkah

– Tipe data kecepatan

– Operator-operator

– Alokasi memori space memori, berkaitan dengan :

• struktur data dinamis

• procedure/function call

• recursif

>>> Tipe data yang digunakan adalah :

– integer

– real

Dua nilai yang sama dengan operator yang sama tetapi dengan variabel yang berbeda,

maka terdapat perbedaan kecepatan / proses penyelesaiannya.

Contoh :

250 + 17 = 267 (lebih cepat dari)

250.0 + 17.0 = 0.25*103 + 0.17*102

= 0.25*103 + 0.017*103

= (0.25+ 0.017)*103

= 0.267*103

= 267.0

Operator

Urutan penggunaan operator/penempatan operator bisa mempengaruhi efisiensi.

Misalkan dalam sebuah perhitungan algoritma terdapat operator perkalian (*) dan

penjumlahan (+), maka operator yang paling mempengaruhi efisiensi adalah perkalian

(*) karena proses perkalian (*) lebih lama daripada proses penjumlahan (+)

• Tetapi dalam perkembangan teknologi, perbedaan penggunaan operator maupun tipe

data dasar tidak terlalu signifikan.

• Yang perlu diperhatikan adalah banyaknya operasi aritmatika dan logika yang

dilakukan.

Operator aritmatika : +, -, *, /, ^.

Operator logika : AND, OR, NOT masing-masing 1 kali operation. Operator adalah

jika hasil perhitungannya termasuk dalam himpunan itu sendiri.

2 < 5 bukan operator tapi konstanta logika karena tidak menghasilkan nilai yang

sejenis

Operator : H x H H

x = 2<5

x = True Tidak ada operation ( 0 operation)

y = 5



y = 5+0 1 operation

y = 2+3*5 2 operation

y = 3*5+2 2 operation

Contoh Program :

Perhatikan potongan program beikut ini yang menghitung jumlah n buah suatu

bilangan riil

Carilah operasi aktif program tersebut dan nyatakan order waktu dalam proses sebagai

fungsi jumlah masukan (n) !!!

Penyelesaian :

Untuk mencari operasi aktif, haruslah di tentukan beberapa kali program eksekusi

pada tiap-tiap bagian.

1. Bagian a, eksukusi satu kali

2. Bagian b, merupakan bagian loop, langkah itu akan diproses berdasarkan kenaikan

harga i dari i = 1 hingga i = n . Jadi, statement sum=sum+v[i] akan diproses sebanyak

n kali sesuai dengan kenaikan harga i

3. Bagian c, akan di proses sekali

Jadi, dapat disimpulkan karena bagian b merupakan bagian yang paling sering

diproses, maka bagian b merupakan operasi aktif. Sedangkan bagian a dan c dapat

diabaikan karena bagian -bagian tersebut tidak diproses sesering bagian b.

Banyak kali bagian b diproses sama banyaknya dengan data yang dimasukan (=n).

Dengan demikian, program penjumlahan n buah bilangan rill memiliki order

sebanding dengan n, dengan kata lain program memiliki O(n).

5302414047 algorithmic efficiency

Documents