TUGAS INDIVIDU I

MATAKULIAH ANALISIS DAN DESAIN ALGORITMA

“APAKAH ALGORITMA YANG OPTIMAL ITU?”

Oleh:

Yuditha Ichsani(G651100321)

Dosen:

Dr. Sri Nurdiati, M.Sc

PASCA SARJANA ILMU KOMPUTER

FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM

INSTITUT PERTANIAN BOGOR

2010

1

APAKAH ALGORITMA YANG OPTIMAL ITU?

Algoritma yang Efisien dan Optimal

Dalam ilmu komputer, efisiensi digunakan untuk menjelaskan sifat dari suatu

algoritma yang berkaitan dengan berapa banyak ragam jenis sumber daya yang

dipakai. Efisiensi algoritmik dapat dianggap sejalan dengan produktivitas rekayasa

untuk proses berulang atau berkelanjutan, yang tujuannya adalah untuk mengurangi

konsumsi sumber daya, termasuk waktu penyelesaian, untuk beberapa level optimal

yang dapat diterima.

Pada umumnya kita tertarik pada sifat-sifat algoritma, seperti berapa lama

waktu dan berapa banyak memori yang dibutuhkan oleh algoritma untuk memperoleh

solusi yang diharapkan. Algoritma umumnya diukur dalam hal jumlah item dari

input, biasanya merujuk pada simbol n. Sebagai contoh ukuran input dari algoritma

pengurutan ialah jumlah item yang akan diurutkan. Suatu algortima yang efisien ialah

algoritma yang menggunakan waktu proporsional pada sebuah fungsi polinomial dari

n, seperti n2.

Beberapa permasalahan memiliki sedikit solusi yang efisien. Misalnya saja

menggunakan waktu yang eksponensial, seperti 2n. Sepintas, mungkin kelihatannya

sangat tidak efisien, tetapi pada prakteknya bahkan komputer yang paling hebat

sekalipun tidak dapat menjalankan algoritma-algoritma yang demikian pada jangka

waktu yang realistis. Permasalahan tersebut tidak dapat diselesaikan secara algoritmik

dan menjadi obyek pada ketertarikan teoritis atau diselesaikan menggunakan teknik-

teknik dari Kecerdasan Buatan (artificial intelligence).

Dalam serangkaian algoritma yang efisien, adalah masih berguna untuk

membandingkan solusi-solusi yang berbeda terhadap masalah yang sama. Sebagian

besar metode pengurutan waktu proporsional pada n2, tetapi ada beberapa yang

mendekati n dalam beberapa keadaan (seperti pada saat inputnya telah hampir

berurutan). Dengan demikian, mungkin lebih baik untuk memilih algoritma yang

dapat berjalan dalam waktu n dibandingkan dengan algoritma yang selalu

menjalankan n2.

2

Waktu bukanlah sesuatu yang selalu dititikberatkan. Namun seringkali

dilakukan pula mempertukarkan waktu dengan ruang memori, dan hal tersebut akan

bergantung pada struktur data yang digunakan untuk menampilkan informasi.

Misalnya, untuk menampilkan alamat pengiriman surat, Anda mungkin hanya

menyimpan kata-kata yang mewakili masing-masing alamat. Sebagai alternatif, Anda

akan mengelompokkan bersama-sama seluruh alamat dalam satu kecamatan, dan lalu

mengelompokkan alamat dalam satu kota dan selanjutnya. Setiap perwakilan akan

mengambil sejumlah memori dan akan membuat beberapa operasi lebih mudah

dibandingkan yang lainnya.

Dengan menyimpan seluruh teks alamat akan memakan banyak ruang

penyimpanan karena nama kecamatan akan disimpan juga pada setiap alamat dalam

kecamatan tersebut, tetapi akan lebih mudah untuk mencetak masing-masing alamat.

Dengan menggunakan struktur data kedua, akan lebih mudah untuk menemukan

seluruh alamat dalam satu kota. Pertukaran ini biasanya menyimpan ruang dalam

struktur data yang berarti akan memakan waktu lebih lama untuk memprosesnya.

Kita dapat menunjukkan secara matematis bahwa suatu solusi (algoritma)

yang memiliki n input akan memiliki waktu proporsional, katakanlah, n2 untuk

berjalan. Beberapa permasalahan memiliki solusi-solusi yang dapat kita cari, tetapi

ada beberapa permasalahan yang lebih kompleks daripada itu. Suatu algoritma

dengan kompleksitas waktu n3 jelas akan memakan waktu lebih lama dibandingkan

n2, tetapi kita kemungkinan dapat menerima hal tersebut; tapi bagaimana jika

kompleksitasnya 2n? Fungsi tersebut akan bertumbuh jauh lebih cepat (lihat gambar

di bawah). Jika n = 64, maka 2n = 1.84 x 1019, atau 18,400,000,000,000,000,000.

Sekiranya komputer dapat mengeksekusi satu juta instruksi yang dibutuhkan untuk

menyelesaikan masalah ini dalam waktu sedetik, maka akan memakan waktu 1.84 x

1013 detik, atau 583,000 tahun.

3

Gambar 1. Perbandingan antara laju pertumbuhan berbeda dari ukuran-ukuran

kompleksitas. Perhatikan bahwa sumbu vertikal di atas adalah skala logaritmik, yang

menunjukkan bahwa kurva 2n tumbuh sangat cepat dibandingkan dengan kurva

lainnya.

Terdapat rangkaian permasalahan lain yang padanya dapat kita temui

algoritma-algoritma polynomial-time, tetapi hanya dengan menggunakan sebuah trik.

Triknya adalah dengan mengasumsikan bahwa Anda memiliki komputer yang

mampu untuk “menebak” dengan tepat solusinya. Kemampuan untuk memilih secara

random solusi yang tepat ini dikenal dengan non-determinism. Tentu saja, tidak ada

komputer non-deterministik yang benar-benar ada: komputer-komputer tersebut

merupakan dasar yang berguna bagi beberapa eksperimen.

Sepertinya permasalahan tersebut hanya dapat diselesaikan pada polynomial-

time, jika tidak ada mesin non-deterministik akan sangat sulit untuk menyelesaikan

dibandingkan yang dapat diselesaikan dengan mesin deterministik yang nyata.

Dengan kata lain, jika rangkaian permasalahan dengan solusi non-deterministik

polinomial adalah NP dan rangkaian permasalahan dengan solusi deterministik

4

polinomial adalah P, lalu keduanya benar-benar berbeda satu sama lain, maka NP ≠

P. Sepertinya adalah tidak mungkin jika NP = P, dan kemudian tidak ada yang

sanggup untuk membuktikan hal tersebut. Hal ini meninggalkan pertanyaan

penelitian terbuka. Ada sesuatu yang tak ternilai harganya yang menanti para

ilmuwan komputer yang dapat membuktikan bahwa NP = P.

Sebuah kontribusi penting yang dapat dilakukan oleh teoris ialah untuk

mengidentifikasi bahwa suatu masalah memiliki algoritma-algoritma yang tidak

efisien (yaitu yang lebih buruk daripada polinomial). Saat ini, meskipun kami

mungkin akan memberitahu programmer untuk tidak ragu-ragu dalam memulai

pengkodean, tapi mungkin untuk memikirkan tentang penyelesaian versi

permasalahan yang lebih sederhana.

Misalnya, kami mungkin mengisinya dengan suatu solusi yang bekerja untuk

sebagian besar – namun tidak semua – input, atau satu hal yang kami ketahui akan

memberikan sesuatu yang mendekati jawaban terbaik (optimal), tetapi tidak ada

jaminan bahwa jawaban tersebut adalah yang terbaik. Umumnya, jika kita sampai

pada titik ini, permasalahan akan menarik dan layak untuk diselesaikan, bahkan jika

tidak mungkin dicapai solusi yang sempurna, lalu kita akan berlanjut pada ranah

Artificial Intelligence, yang cenderung melakukan pendekatan yang sangat berbeda

pada masalah-masalah ini.

Pada intinya, suatu algoritma dikatakan optimal pada worstcase-nya jika tidak

ada algoritma lain yang sekelas yang melakukan lebih sedikit operasi dasar. Adapun

cara untuk memeriksa optimalitas algoritma secara umum ialah yang pertama

menentukan batas bawah dari jumlah operasi yang diperlukan untuk menyelesaikan

masalah, selanjutnya dapat dikatakan bahwa sembarang algoritma yang melakukan

operasi sejumlah batas bawah tersebut berarti optimal

Untuk memeriksa optimalitas algoritma, langkah-langkahnya ialah:

1. Buat algoritma yang efisien (A). Analisis A dan tentukan sebuah fungsi W,

sedemikian sehingga A mengerjakan paling banyak W(n) langkah pada worst-

casenya. Dhi, n adalah ukuran input.

5

2. Untuk beberapa fungsi F, buktikan teori yang menyatakan bahwa sembarang

algoritma dalam kelas yang dipelajari, terdapat ukuran input n yang

menyebabkan algoritma tersebut melakukan paling sedikit F(n) langkah.

Jika W = F, maka algoritma A optimal pada worst-casenya. Jika W ≠ F,

mungkin terdapat algoritma yang lebih baik atau ada batas bawah yang lebih baik.

Worst-Case dan Average-Case

Worst-case merupakan jenis analisis yang biasa digunakan pada algoritma.

Analisis worst-case dapat dikatakan sebagai waktu maksimum yang dibutuhkan oleh

algoritma untuk melakukan operasi pada setiap input yang memiliki ukuran n. Batas

waktu worst-case (worst-case time bounds) artinya suatu batas pada waktu yang

berjalan yang mempergunakan setiap kemungkinan yang mungkin terjadi pada

permasalahan yang dihadapi. Batas waktu worst-case bukanlah satu-satunya hal yang

menarik. Kadang kala kita mungkin tidak peduli bila suatu algoritma terkadang

menjadi sangat lambat selama algoritma tersebut “hampir selalu cepat”. Pada situasi

lain, kita mungkin cukup puas dengan suatu algoritma yang memiliki kecepatannya

rata-rata. Untuk saat ini, bagaimanapun juga kita akan berpaku pada batas waktu

worst-case dan mempelajari beberapa teori yang berkenaan dengan situasi tersebut.

Analisis kinerja worst-case dan analisis kinerja average-case memiliki

beberapa kesamaan, tetapi dalam prakteknya biasanya membutuhkan tool dan

pendekatan yang berbeda. Menentukan apa arti dari input rata-rata sulit, dan sering

bahwa input rata-rata memiliki sifat yang membuatnya sulit untuk dicirikan secara

matematis (misalnya, algoritma yang dirancang untuk beroperasi pada string teks).

Demikian pula, bahkan ketika penjelasan yang masuk akal dari "average-case"

adalah mungkin, mereka cenderung lebih sulit untuk menganalisis persamaan.

Analisis worst-case memiliki masalah yang serupa, yaitu biasanya tidak

mungkin untuk menentukan skenario worst-case secara tepat. Sebaliknya, sebuah

skenario diusahakan sedemikian rupa sehingga paling tidak menjadi seburuk worst-

case. Misalnya, ketika menganalisis algoritma, dimungkinkan untuk menemukan

6

jalur/path paling panjang melalui algoritma (dengan mempertimbangkan jumlah

maksimal loop, misalnya) bahkan jika tidak mungkin untuk menentukan input secara

tepat yang akan menghasilkan jalur ini. Hal ini memberikan analisis yang aman,

namun ada pula yang pesimis, karena mungkin tidak ada input yang akan

menghendaki jalur ini.

Di lain pihak, skenario yang dianggap mendekati worst-case yang sebenarnya

dapat dipertimbangkan. Hal ini dapat mengarahkan pada hasil yang optimis, yang

berarti bahwa analisis benar-benar dapat meremehkan worst-case yang sebenarnya.

Dalam beberapa situasi Anda mungkin perlu untuk menggunakan analisis pesimistik

untuk menjamin keamanan. Namun seringkali, analisis pesimistik mungkin terlalu

pesimis, sehingga analisis yang semakin dekat dengan nilai sebenarnya, namun

mungkin optimis dapat menjadi pendekatan yang lebih praktis.

Ketika menganalisis algoritma-algoritma yang sering memakan sedikit waktu

untuk diselesaikan, tetapi secara berkala membutuhkan waktu yang jauh lebih besar,

amortized analysis dapat digunakan untuk menentukan lama perjalanan rata-rata pada

worst-case yang mungkin saja tak terbatas selama beberapa seri operasi. Biaya pada

amortized analysis ini dapat lebih mendekati biaya average-case, sementara masih

memberikan batas atas (upper bound) yang terjamin pada lamanya perjalanan

(running time).

REFERENSI:

Cormen, T., C. Leierson, R. Rivest dan C. Stein, Introduction to Algorithms, Second Edition, McGraw-Hill, New York, 2001.

Edwards, A., Get Set for Computer Science, Edinburgh University Press, Edinburgh, 2006.

Kalos, L. S. dan G. Marton, Worst-Case Versus Average Case Complexity of Ray-Shooting, Technical University of Budapest, Budapest, 1995.

Knuth D., Structured Programming with go to Statements, Computing Surveys, Vol. 6, No. 4, Stanford University, Stanford, 1974.

Wilf, H., Algorithm and Complexity, University of Pennsylvania, Philadelphia, 1994.

7