• Desain dan Analisis Algoritma; Sebuah Pengantar

    Hallo semua, kali ini saya akan mencoba menulis sebuah artikel tentang Desain dan Analisis Algoritma. Anak ilmu komputer, teknik informatika, matematika tentu sudah sangat familiar dengan tema ini. Namun tak ada salahnya kita coba ulas kembali untuk menyegarkan ingatan kita. Sippps?! Namun, sebelum kita bahas terlalu dalam, alangkah baiknya kita mengulang beberapa hal.

    Secara umum, algoritma adalah sebuah prosedur atau langkah-langkah komputasi yang terdifinisikan dengan baik yang membutuhkan nilai/kumpulan nilai sebagai inputnya dan menghasilkan nilai/kumpulan nilai sebagai outputnya. Dari definisi ini maka bisa kita ambil kata kunci bahwa algoritma itu terdiri dari 3 elemen, ada input, proses, dan output. Algoritma ini digunakan untuk menyelesaikan permasalahan komputasi yang jelas (masalahnya harus jelas ya hehe). Biasanya, dalam sebuah permasalahan komputasi akan tergambarkan bagaiamana hubungan antara input dan output. Contoh sederhananya misalkan permasalahan Sorting. Dalam permasalahan ini hubungan antara input dan output bisa digambarkan sebagai output merupakan himpunan yang sama dengan input namun dalam keadaan terurut. Jadi elemen input sama dengan elemen output, tidak ada tambahan atau pengurangan elemen. Apabila permasalahan Sorting ini kita petakan ke 3 elemen algoritma, maka inputnya adalah sembarang bilangan dengan sembarang urutan, prosesnya adalah cara kita mengolah bilangan tersebut sampai terurut, sedangkan outputnya adalah bilangan input dalam keadaan terurut.

    Algoritma yang dibentuk harus benar sehingga permasalahan tersebut dapat diselesaikan. Algoritma dikatakan benar apabila untuk setiap instance (contoh) dari sebuah permasalahan yang diberikan  berhenti (halt) dengan output yang benar. Bukan berhenti karena hang atau permasalahan yang lainnya. Atau algoritmanya berjalan terus (infinite loop) tanpa ada titik selesai. Khusus untuk sistem real-time, maka syaratnya bertambah yaitu algoritmanya mampu menyelesaikan permasalahan itu dalam batas waktu tertentu. Algoritma yang salah biasanya tidak akan berhenti pada kasus input tertentu atau berhenti pada output yang tidak seharusnya. Namun, ada beberapa algoritma yang tidak benar namun bisa diterima dengan toleransi tertentu. Misalnya algoritma Miller-Rabin untuk mencari bilangan prima. Jadi kesimpulannya, kebenaran suatu algoritma dilihat dari kemampuannya untuk menghasilkan output yang benar dan berhenti pada output tersebut.

    Namun adakalanya suatu algoritma benar akan tetapi tidak efisien. Efisiensi ini biasanya diukur dari waktu dan sumber daya yang dibutuhkan suatu algoritma untuk menyelesaikan suatu masalah. Algoritma yang efisien akan menghasilkan suatu performa program yang lebih baik. Ada orang yang bilang, tidak usah belajar algoritma, toh dengan kemampuan komputer saat ini kita bisa menyelesaikan permasalahan komputasi dengan lebih mudah. Secara kasat mata mungkin pernyataan ini ada benarnya. Namun jika kita teliti lebih jauh akan sangat terasa perbedaan program yang menggunakan algoritma yang efisien dan tidak. Misalkan kita bandingkan algoritma berikut :

    Algoritma Insertion Sort yang membutuhkan waktu c1 n^2
    Algoritma Merge Sort yang membutuhkan waktu c2 n lg n

    di mana c1 <  c2 dan n adalah jumlah elemen input.  Variabel c ini tidak akan terlalu berpengaruh karena akan ada suatu nilai di mana waktu yang dibutuhkan kedua algoritma tersebut untuk menyelesaikan permasalahan akan bersilangan yang menunjukkan Merge Sort lebih cepat. Bisa diperhatikan bahwa variabel yang berpengaruh adalah n.

    Anggaplah ada dua komputer dengan kecepatan 10^9 instruksi/detik (komputer A) dan 10^7 instruksi/detik (komputer B). Bisa dilihat bahwa komputer A 100 kali lebih cepat dari komputer B. Percobaan kita mulai. Insertion Sort dijalankan pada komputer A dan Merge Sort pada komputer B yang lebih lambat. Jadi skemanya sebagai berikut :

    Apabila komputer ini mengurutkan 1 juta bilangan (n) maka kita bisa menghitung waktu yang dibutukan kedua komputer tersebut sebagai berikut :

    Komputer A = 2 * (10^6)^2 instruksi/10^9 instuksi/detik = 2000 detik
    Komputer B = 50 * (10^6) * lg (10^6) /10^7 instruksi/detik ≈100 detik

    Dari percobaan sederhana ini dapat kita lihat bahwa dengan algoritma yang efisien maka komputer yang 100 kali lebih lambat dapat menyelesaikan permasalahan Sorting 20 kali lebih cepat dengan algortima yang efisien. Coba dibandingkan apabila komputernya sama, maka berapa besar selisih waktu yang dibutuhkan. Hitung sendiri ya guys.

    Kebayangkan kenapa kita harus belajar mendesain algoritma dan menganalisisnya. Hari ini begitu banyak permasalahan yang belum tersedia algoritma penyelesaiannya sehingga terkadang kita harus mengembangkan sendiri algoritmanya. Terdapat juga permasalahan rumit yang terangkum dalam NP-Complete (Nondeterministic Polynomial) yang membutuhkan algoritma yang efisien untuk menyelesaikannya. Programmer yang memiliki pondasi yang kuat terhadap ilmu algoritma akan mampu melakukan banyak hal untuk menyelesaikan berbagai permasalahan komputasi. Ingat, algoritma adalah inti dari sebagian besar teknologi komputer yang kita gunakan hari ini. Jadi tidak ada ruginya kita mempelajarinya kan?

    Sekian dulu untuk saat ini. Artikel selanjutnya akan kita bahas hubungan algoritma dan struktur data. Jika kamu ada pertanyaan, komentar, atau kritik tentang tulisan ini, silahkan tinggalkan komenmu di kolom komentar. See you next time bro…

     

    Muhammad Nur Musa

    Universitas Indonesia

    Comments

    comments

Leave a Reply

%d bloggers like this: