Penjelasan Sederhana Tentang Algoritma & Big-O Notation
Ditulis oleh : Farhan Rivaldy
Halo Teman-teman, artikel kali ini bisa dibilang merupakan sambungan dari artikel yang pernah Saya tulis sebelumnya :
Namanya juga manusia tak luput dari kesalahan, Saya sendiri bukan orang yang berkompeten di bidang computer science tapi Saya harap seiring waktu Saya bisa memperbaiki diri.
Kesalahan Saya di artikel tersebut adalah tidak menjelaskan dari basic, seperti apa itu algoritma, apa itu Big-O Notation, Mengapa struktur data itu sangat dibutuhkan, dan mengapa Kita setidaknya harus paham sedikit alasan mengapa Kita membutuhkan hal tersebut.
Di artikel Kali ini Saya akan mencoba untuk memperbaiki KESALAHAN tersebut, so…. Happy Reading!.
Berkenalan Dengan Algoritma
Sebagai programmer, sudah menjadi kewajiban Kita untuk menyelesaikan masalah, tentunya cara Kita menyelesaikan masalah tersebut harus efektif dan efisien. Kalau tidak efektif dan efisien lantas apa yang sudah Kita kerjakan sebenarnya?.
Untuk bisa menyelesaikan masalah dengan efektif dan efisien Kita perlu tahu permasalahan yang ingin Kita selesaikan, serta cara bagaimana Kita menyelesaikan masalah tersebut. Untuk itu Kita membutuhkan yang namanya algoritma.
Apa itu algoritma?
In mathematics and computer science, an algorithm is a finite sequence of well-defined instructions, typically used to solve a class of specific problems or to perform a computation(wikipedia)
Singkatnya algoritma adalah urutan proses yang dilakukan secara berurutan untuk menyelesaikan suatu permasalahan sehingga bisa menyelesaikan permasalahan secara efektif dan efisien. Di kehidupan sehari-hari Kita tidak lepas dari algoritma itu sendiri, contoh :
- Ketika Kita memasak suatu masakan yang mengikuti resep,
- Ketika Kita ingin pergi ke suatu tempat, Seperti kata pepatah “Banyak jalan menuju Roma”. Tentunya ada banyak sekali rute yang bisa Kita lewati, Tentunya Kita akan melewati rute yang cepat untuk sampai tujuan
Dalam konteks computer science, Algoritma ada banyak sekali jenisnya tergantung permasalahan yang ingin Kita selesaikan dan perlu Teman-teman ingat bahwa algoritma bisa Kita terapkan lebih dari satu bahasa pemrograman.
Dari sudut pandang struktur data, berikut beberapa kategori penting dari algoritma :
- Search : Algoritma yang bertujuan untuk mencari sebuah data di dalam struktur data
- Sort : Algoritma yang bertujuan untuk mengurutkan data dalam urutan tertentu
- Insert : Algoritma yang bertujuan untuk memasukan sebuah data di dalam struktur data
- Update : Algoritma yang bertujuan untuk mengubah sebuah data yang sudah ada sebelumnya di struktur data
- Delete : Algoritma yang bertujuan untuk menghapus sebuah data yang sudah ada sebelumnya di struktur data
Bagaimana Cara Menulis Algoritma Dengan Baik
Sebenarnya tidak ada standar baku dalam penulisan algoritma, dan perlu teman-teman ketahui bahwa tidak semua urutan proses atau prosedur bisa disebut algoritma, sebuah algoritma harus mengikuti kateristik dibawah ini :
- Unambiguous : Algoritma yang ditulis harus jelas dan tidak ambigu. setiap langkah atau fase dan input/output harus jelas mengarah pada satu makna
- Input : Algoritma harus memiliki 0 atau lebih input yang terdefinisi dengan baik
- Output : Algoritma harus memiliki 1 atau lebih output yang terdefinisi dengan baik dan harus sesuai dengan keluaran yang diinginkan
- Finiteness : Algoritma harus dihentikan setelah menyelesaikan tahapan
- Feasibility : Algoritma harus bisa berjalan dengan layak dengan sumber daya yang tersedia
- Independent : Algoritma harus memiliki petunjuk selangkah demi selangkah, yang harus independen dari kode pemrograman apa pun.
Big-O Notation
Ketika Kita selesai menulis sebuah kode yang sudah menyelesaikan permasalahan, lantas apa sampai disitu saja? Tentu tidak Ferguso….
Kita harus memikirkan apakah kode yang Kita ciptakan sudah efektif dan efisien.
Bagaimana Kita bisa tahu kode yang Kita ciptakan sudah efektif dan efisien? Big-O Notation hadir untuk menyelesaikan pertanyaan tersebut.
Sebenarnya Apa itu Big-O Notation?
Big-O Notation atau dalam bahasa Indonesianya Notasi O besar adalah salah satu cara untuk mengukur tingkat kompleksitas suatu algoritma.
Kenapa Kita perlu Big-O Notation?
Katakanlah kode yang sudah Kita buat dan dijalankan di laptop Kita butuh waktu sekitar 3 detik. Waktu 3 detik tersebut tidak bisa Kita jadikan patokan bahwa kode yang sudah Kita buat berjalan dengan cepat, ada banyak sekali faktor yang mempengaruhi seperti : jumlah datanya, koneksi, latensi, jumlah memori, kecepatan prosesor dan lainnya. Bisa jadi di laptop yang berbeda akan memakan waktu yang lebih cepat atau lebih lama tergantung faktor yang Saya sebutkan diatas.
Untuk menghitung kompleksitas kode yang sudah Kita buat Kita ada dua hal yang perlu Kita cari pertimbangkan, yang pertama Space Complexity dan yang kedua Time Complexity.
Apa Itu Space Complexity?
Space Complexity adalah seberapa besar memori yang digunakan untuk menjalankan suatu algoritma.
Apa Itu Time Complexity?
Time Complexity adalah seberapa lama waktu yang kita dihabiskan untuk menjalankan suatu algoritma.
Waktu yang dibutuhkan oleh suatu algoritma ada tiga jenis :
- Best Case : Waktu minimum yang diperlukan untuk eksekusi program
- Average Case : Rata-rata waktu yang dibutuhkan untuk eksekusi program
- Worst Case : Waktu maksimum yang diperlukan untuk eksekusi program
Di Artikel kali ini Kita akan fokus terhadap Time Complexity, Ada berbagai macam Time Complexity, diantaranya :
O(1) Constant Time
Ini adalah yang ideal, tidak peduli berapa banyak item yang ada di dalam struktur data, apakah satu atau satu juta, jumlah waktu untuk menyelesaikannya akan tetap sama.
Kebanyakan operasi yang melakukan operasi tunggal adalah O(1). Seperti : menambahkan data ke array, mendapatkan item pada indeks array tertentu, menambahkan elemen child, dan lain sebagainya, semua akan memakan waktu yang sama.
Perhatikan kode berikut :
Kita punya dua array, smallArray memiliki 5 item sedangkan bigArray memiliki 50 item, untuk yang pertama Kita coba untuk memasukan data ke dalam smallArray, dan ternyata hanya membutuhkan waktu kurang dari 1 milisecond
Bagaimana dengan bigArray, apakah waktu yang dibutuhkan juga kurang dari 1 milisecond?
Yups…. tepat sekali, kurang dari 1 milisecond untuk mengoperasikannya, tidak peduli berapa banyak datanya waktu yang dihabiskan akan selalu sama atau constant.
O(n) Linear Time
Secara default, semua loop adalah contoh pertumbuhan linier karena ada hubungan satu-ke-satu antara ukuran data dan waktu penyelesaian. Jadi array dengan 1.000 kali lebih banyak item akan memakan waktu tepat 1.000 kali lebih lama.
Perhatikan kode berikut :
untuk yang pertama Kita coba untuk loop semua data smallArray, dan ternyata membutuhkan waktu 3 milisecond, bagaimana dengan bigArray?
Perhatikan kode berikut :
Ternyata bigArray memerlukan waktu 18 milisecond, yang artinya 6x lipat dibandingkan sebelumnya
O(n²) Quadratic Time
Terkadang Kita perlu menemukan pasangan yang cocok untuk setiap item dalam array? nested loop adalah cara yang bagus untuk menyelesaikan masalah tesebut, tapi tidak disarankan. Mengapa? array dengan 1.000 item akan menjadi satu juta pencarian operasi yang akan membuat browser Kita freeze.
Perhatikan kode berikut :
untuk yang pertama Kita coba untuk nested loop semua data smallArray, dan ternyata membutuhkan waktu 16 milisecond, bagaimana dengan bigArray?
Hasilnya bigArray memerlukan waktu 584 milisecond, yang artinya 36x lipat dibandingkan sebelumnya.
Oleh karena itu disarankan untuk menghindari nested loop sebisa mungkin karena sangat memakan banyak memori dan waktu.
O(log n) Logarithmic Time
logaritmic Time O(log n) adalah yang tercepat setelah O(1). Runtime logaritmic time biasanya berlaku untuk algoritma yang membagi masalah menjadi setengah langkah, salah satu contohnya adalah binary search.
Binary search digunakan untuk mencari posisi nilai dari suatu array yang sudah diurutkan. Saya secara khusus men-higlight diurutkan karena array harus diurutkan untuk mendapatkan hasil yang akurat dengan algoritma ini. Ingatlah ini ketika teman-teman ingin menggunakan binary search.
Bayangkan Ketika Kita punya array sebanyak 10 item dan Kita ingin mencari value 5, Apa yang bisa Kita lakukan? menggunakan for loop tentunya bisa menyelesaikan permasalahan tersebut. Metode ini bisa juga disebut Brute Force Solution.
Perhatikan kode berikut :
Kode diatas merupakan notasi O(n) atau Linear Time, seperti yang Kita ketahui waktu yang diperlukan O(n) tergantung n itu sendiri. semakin banyak jumlah n-nya maka semakin lama pula waktu yang dibutuhkan.
Bayangkan jika n-nya ada ratusan, ribuan atau bahkan jutaan? untuk mencari sebuah data di 100 item tentunya akan memakan waktu 10 kali lebih lama dibandingkan jika Kita hanya mencari data di 10 item .
Lantas bagaimana cara mengatasi masalah tersebut? untuk itu Kita perlu menggunakan binary search.
Perhatikan kode berikut :
Lah kok malah makin lambat make binary search? katanya efisien untuk masalah ini? oke² harap bersabar…… Bagaimana Kita coba tambah item arraynya menjadi sejuta dan Kita cari itemnya agak banyak sedikit?
Perhatikan kode berikut :
Gimana…. sudah keliatan kan perbedaannya? jika datanya ada banyak maka binary search akan jauh 10x lebih cepat dibandingkan linear search yang menggunakan loop biasa, dengan perbandingan ini Saya harap teman-teman bisa memilih algoritma yang benar untuk menyelesaikan suatu permasalahan.
O(n!) Factorial Time
Factorial merupakan hasil dari perkalian bilangan bulat positif sampai dengan bilangan tersebut, biasanya ditulis dengan tanda seru dibelakang angkanya (n!), contoh faktorial sebagai berikut :
5! = 5x4x3x2x1 = 120
Factorial bisa Kita gunakan untuk menyelesaikan beberapa masalah, salah satunya yang terkenal yaitu Travelling Salesman Problem. Apa sih sebenarnya Travelling Salesman Problem? Singkatnya adalah, katakanlah Kita adalah seorang sales yang harus mengunjungi kota sebanyak n. Rute mana yang terpendek untuk mengunjungi setiap kota lalu kembali ke kota tempat Kita memulai perjalanan? Untuk menyelesaikan permasalahan ini Kita perlu menghitung setiap kemungkinan rute yang akan dilewati.
Untuk contoh kali ini Kita perlu mengunjungi 3 Kota, ada berapa mutasi yang Kita punya atau ada berapa kemungkinan rute yang akan Kita lewati?
3! = 3x2x1 = 6 kemungkinan rute
Perhatikan kode berikut :
Jika Kita perlu melewati 3 kota berbeda, dalam kasus ini
[“Balikpapan” , “Samarinda”, “Tenggarong”] maka Kita akan punya 6 permutasi atau 6 kemungkinan rute yang memakan waktu sebanyak 3.5 milisecond.
0: (3) [‘Balikpapan’, ‘Samarinda’, ‘Tenggarong’]
1: (3) [‘Balikpapan’, ‘Tenggarong’, ‘Samarinda’]
2: (3) [‘Samarinda’, ‘Balikpapan’, ‘Tenggarong’]
3: (3) [‘Samarinda’, ‘Tenggarong’, ‘Balikpapan’]
4: (3) [‘Tenggarong’, ‘Balikpapan’, ‘Samarinda’]
5: (3) [‘Tenggarong’, ‘Samarinda’, ‘Balikpapan’]
Apa yang terjadi bila Kita mencoba menghitung 20 kota? yang artinya ada 2,432,902,,008,176,640,000 kemungkinan rute. silahkan teman-teman untuk mencoba sendiri karena laptop Saya sendiri hanya mampu menghitung sampai 10 kota saja.
Refrensi :
PENUTUP
Pada artikel ini Saya rasa cukup sampai disini saja dulu, bila teman-teman masih bingung dengan tulisan Saya ini bisa mengajukan pertanyaan atau ada hal yang ingin dibahassilahkan komentar dibawah…
Dengan memahami Big O Notation, Kita akan sadar betapa pentingnya memilih algoritma untuk menyelesaikan suatu permasalahan, tidak asal jadi yang penting kode yang Kita buat berjalan tanpa memikirkan space & time complexity.
Kurang lebihnya mohon dimaafkan, bila ada saran dan kritik sangat dipersilahkan sekali demi menambah wawasan setiap orang yang membaca artikel ini.
Jangan lupa follow akun medium Saya Farhan Rivaldy dan DSC Mulia University agar bisa mendapatkan pengetahuan lainnya.
Sekian dan terima kasih
じゃあね ー See you
“Talk is cheap, show me the code.” — Linus Torvalds
