Algoritma dan Kompleksitas Waktu

1. Algoritma

Algoritma adalah deskripsi langkah-langkah penyelesaian masalah yang tersusun secara logis atau urutan logis pengambilan keputusan untuk pemecahan suatu masalah. Algoritma ditulis dengan notasi khusus, notasi mudah dimengerti dan notasi dapat diterjemahkan menjadi sintaks suatu bahasa pemrograman.

Algoritma merupakan salah satu cabang ilmu komputer yang membahas prosedur penyelesaian suatu permasalahan. Dengan algoritma yang baik maka komputer bisa menyelesaikan perhitungan dengan cepat dan benar. Sebaliknya jika algoritma kurang baik maka penyelesaian lambat dan bahkan tidak didapat solusi yang diharapkan.

Suatu algoritma akan memerlukan masukan (input) tertentu untuk memulainya, dan akan menghasilkan keluaran (output) tertentu pada akhirnya. Hal-hal yang perlu diperhatikan dalam algoritma adalah mencari langkah-langkah yang paling sesuai untuk penyelesaian suatu masalah, karena setiap algoritma memiliki karakteristik tertentu yang memiliki kelebihan dan kekurangan. Beberapa hal yang harus dipahami dalam mencari algoritma antara lain:

1.      Masalah seperti apa yang hendak diselesaikan.

2.      Gagasan apa yang ada pada algoritma tersebut.

3.      Berapa lama yang diperlukan untuk menyelesaikan masalah.

4.      Berapa jumlah data yang dapat ditangani oleh suatu algoritma.

2.    Kompleksitas Waktu

Sebuah algoritma tidak saja harus menghasilkan keluaran yang benar, tetapi juga harus mangkus (efisien). Kebenaran suatu algoritma harus diuji dengan jumlah masukan tertentu untuk melihat kinerja algoritma berupa waktu yang diperlukan untuk menjalankan algoritmanya dan ruang memori yang diperlukan untuk struktur datanya.

Algoritma yang bagus adalah algoritma yang mangkus (efisien). Kemangkusan algoritma diukur dari berapa jumlah waktu dan ruang memori yang dibutuhkan untuk menjalankan algoritma tersebut. Algoritma yang mangkus adalah algoritma yang meminimumkan kebutuhan waktu dan ruang.

Implementasi sebuah algoritma dapat dikatakan baik atau efisien adalah memerlukan kriteria formal yang digunakan untuk menilai algoritma tersebut yaitu kemangkusan algoritma dengan kompleksitasnya. Besaran yang dipakai untuk menerangkan model penilaian waktu/ruang algoritma adalah dengan menggunakan kompleksitas algoritma.

Ada dua macam kompleksitas algoritma, yaitu kompleksitas waktu dan kompleksitas ruang. Kompleksitas waktu dari algoritma adalah mengukur jumlah perhitungan (komputasi) yang dikerjakan oleh komputer ketika menyelesaikan suatu masalah dengan menggunakan algoritma. Ukuran yang dimaksud mengacu ke jumlah langkah-langkah perhitungan dan waktu tempuh pemrosesan.

Kompleksitas waktu merupakan hal penting untuk mengukur efisiensi suatu algoritma. Kompleksitas waktu dari suatu algoritma yang terukur sebagai suatu fungsi ukuran masalah.

Kompleksitas waktu dari algoritma berisi ekspresi bilangan dan jumlah langkah yang dibutuhkan sebagai fungsi dari ukuran permasalahan. Kompleksitas ruang berkaitan dengan sistem memori yang dibutuhkan dalam eksekusi program. Pada tabel di bawah diperlihatkan kelompok algoritma berdasarkan kompleksitas waktu asimptotiknya.

  

Kelompok Algoritma	Nama
O(1)	Konstan
O(log n)	Logaritmik
O(n)	Linear
O(n log n)	n log n
O(n2)	Kuadratik
O(n3)	Kubik
O(2n)	Eksponensial
O(n!)	Faktorial

Berdasarkan tabel di atas, maka dapat digambarkan grafik kelompok algoritma dengan kompleksitas waktu asimptotiknya seperti yang terlihat pada gambar berikut:

 

Kebutuhan waktu dan ruang suatu algoritma bergantung pada ukuran masukan, yang secara khas adalah jumlah data yang diproses. Ukuran masukan itu disimbolkan dengan n. Setelah menetapkan ukuran masukan, maka langkah selanjutnya dalam mengukur kompleksitas waktu adalah menghitung banyaknya operasi yang dilakukan algoritma sehingga didapatkan notasi kompleksitas waktunya dalam fungsi n yaitu f(n).

Untuk mengukur kebutuhan waktu sebuah algoritma yaitu dengan mengeksekusi langsung algoritma tersebut pada sebuah komputer, lalu dihitung berapa lama durasi waktu yang dibutuhkan untuk menyelesaikan sebuah persoalan dengan n yang berbeda-beda. Kemudian dibandingkan hasil komputasi algoritma tersebut dengan notasi kompleksitas waktunya untuk mengetahui efisiensi algoritmanya.

DAFTAR PUSTAKA / REFERENSI

Gloor, P. A., Johnson, D. B., Makedon, F., Metaxas, P., (1993), A Visualization System for Correctness Proofs of Graph Algorithms, http://www.wellesley.edu/CS/pmetaxas/visual_proofs.pdf, Computer Science Education, [19 Maret 2010].

Greenberg, H. J., (1998), Greedy Algorithm for Minimum Spanning Tree, http://glossary.computing.society.informs.org/notes/spanningtree.pdf, University of Colorado, Denver, [19 Maret 2010].

Kristanto, A., (2008), Perancangan Sistem Informasi dan Aplikasinya, Gava Media, Yogyakarta.

Mehta, D. P., Sahni, S., (2005), Handbook of Data Structures and Applications, Chapman & Hall/CRC Computer and Information Science Series, United States of America.

Munir, R., (2009), Matematika Diskrit, Edisi 3, Informatika, Bandung.

Oetomo, B. S., (2002), Perencanaan dan Pembangunan Sistem Informasi, Andi, Yogyakarta.

Pop, P. C., Zelina, I., (2004), Heuristic Algorithms for the Generalized Minimum Spanning Tree Problem, http://emis.library.cornell.edu/ journals/AUA/acta8/Pop_Zelina.pdf, Proceedings of the International Conference on Theory and Applications of Mathematics and Informatics (ICTAMI), Thessaloniki, Greece, [19 Maret 2010].

Purbasari, I. Y., (2007), Desain Dan Analisis Algoritma, Edisi 1, Graha Ilmu, Yogyakarta.

Purwanto, E. B., (2008), Perancangan Dan Analisis Algoritma, Edisi 1, Graha Ilmu, Yogyakarta.

Zakaria, T. M., Prijono, A., (2006), Konsep Dan Implementasi Struktur Data, Informatika, Bandung.