Algoritma - Teori

Algoritma merupakan prosedur langkah demi langkah untuk mendefinisikan satu set instruksi agar dieksekusi pada urutan tertentu sehingga mendapatkan output yang diinginkan, biasa dibuat independen tergantung dari bahasa yang mendasari. Pada algoritma terdapat klasifikasi order of growth, yang sangat penting karenanya kinerja algoritma menjadi sangat bervariasi.

photo/photo/man-standing-infront-of-white-board-1181345/

Seringkali kita harus berpikir tentang berbagai cara menganalisis algoritma tergantung pada input-nya. Perlu diingat pada materi sebelumnya, bahwa penggunaan algoritma diperlukan beberapa petimbangan, yang mana aturannya harus benar, artinya output yang sama sesuai dengan jumlah instruksi yang dimasukkan. Maka ketika algoritma yang dimasukkan salah, maka salah juga outputnya. Kemudian sejauh mana hasil output algoritma yang dibuat, karena Sebuah algoritma harus sebaik mungkin memiliki hasil yang dekat dengan hasil sebenarnya. Lantas harus efisiensi baik dari kapasitas memori dan waktu. Meski algoritma yang dibuat telah memiliki hasil yang tepat atau mendekati namun jika memerlukan waktu yang panjang untuk menunggu hasilnya, algoritma tersebut tidak layak dipakai, apalagi jika kapasitas memori dipakai terlalu banyak, maka algoritma tersebut kurang baik.

Harus diingat bahwa running time atau waktu berjalan, akan berada di antara kasus terbaik dan kasus terburuk. Kasus terbaik adalah batas bawah biaya dari algoritma maka kita harus menganalisa dan memberi garansi bahwa running time pada algoritma Tidaklah lebih besar ketika anda memberi input. Dan dalam banyak situasi kita juga mungkin harus mempertimbangkan input yang menjadi acak. Maka bagaimanapun dalam memodelkan, apa yang kita maksudkan acak untuk suatu masalah dapat diselesaikan, namun dalam banyak situasi kita harus melakukan atau memprediksi performance-nya nanti meski inputnya sangat bervariasi. Jadi nanti singkatnya semua orang dapat menyelesaikan masalah menggunakan algoritma meski urutan-urutan yang berbeda-beda, tapi hasilnya sama.

Misalnya untuk 3-sum (Dalam teori kompleksitas komputasional, masalah 3SUM menanyakan apakah seperangkat n {\ displaystyle n} n bilangan real berisi tiga elemen yang berjumlah nol), itu selalu sama. Dengan notasi tilde, satu-satunya variabilitas dalam algoritma bahwa beberapa kali jumlah counter bertambah namun berada pada kondisi rendah tapi tidak perlu mempermasalahkan analisa yang dibuat. Misal pada Algoritma pencarian binary, anda mungkin sudah berada pada jalan yang tepat dalam sebuah kasus secara konstan waktu dan kita bisa menunjukkan rata-rata dan kasus terburuknya pada keduanya dengan lg based two(N).

Contoh lainnya jauh lebih dari variabilitas, Jadi kita punya analisis yang berbeda namun tergantung pada inputnya. Namun pertanyaannya adalah, bagaimana dengan masalah sebenarnya yang ingin diselesaikan klien? Jadi kita harus memahami bahwa ada dua urutan agar dapat memahami kinerja algoritma, sehingga ada dua pendekatan terjadi yang berhasil dan salah satunya adalah desain untuk kasus terburuk. Hanya untuk memastikan bahwa algoritma Anda selalu berjalan dengan cepat dan itu sangat ideal. Namun selain itu kalau Anda tidak bisa melakukan secara random kemudian bergantung pada beberapa jaminan probabilistic maka akan bisa dilihat pada prosesnya nanti.

Kemudian ada jenis considerations, kita paham bahwa ide dari order of growth atau urutan pertumbuhan, sebenarnya inti dari teori algoritma itu sendiri. Maka goal kita dalam algoritma adalah kita punya masalah, anggap seperti menyelesaikan 3-sum tadi dan itu sangat sulit. Maka kita mesti mencari algoritma terbaik untuk penyelesaian masalah tersebut. Maka pendekatan para ilmuwan computer adalah mencoba menekan sebanyak mungkin perincian kemungkinan dalam analisis. Dan memilih menganalisa running time ke dalam faktor konstan.

Itulah bagaimana order of growth diperoleh dan anda tak akan mengkhawatirkan model input apapun. Jika fokus pada desain kasus terburuk dan berbicara bagaimana kinerja algoritma berdasarkan urutan pertumbuhan, maka itu sangat mungkin. Karena disini anda akan sangat teliti dalam membuat algoritma ketika memecahkan masalah yang sulit.

Lebih jelasnya, Tingkat kerumitan algoritma dilihat bagaimana ukuran banyaknya proses yang dibutuhkan oleh algoritma ketika dalam menyelesaikan suatu masalah, jika mampu memecahkan atau menyelesaikan suatu permasalahan dalam waktu yang singkat memiliki tingkat kerumitan yang rendah, sebaliknya algoritma yang membutuhkan waktu yang lama dalam penyelesaian masalah maka itu memiliki tingkat kompleksitas yang tinggi

Setelah memahami teori ini, anda sudah mempunyai mindset atau goal untuk menemukan algoritma yang optimal sehingga menjamin hasil faktor konstan dengan kinerja tertentu untuk setiap input meskipun kadang muncul kasus terburuk.

Baik contohnya seperti ini, Order of growth hanya memberikan deskripsi kasar pada perilaku suatu proses. Misalnya, sebuah proses yang membutuhkan langkah-langkah n^2 dan dan proses yang membutuhkan langkah-langkah 1000n^2 dan proses yang membutuhkan langkah 3n^2 + 10n + 17, maka semuanya memiliki urutan pertumbuhan O(n^2)

Maka Urutan pertumbuhan memberikan indikasi yang berguna tentang bagaimana kita dapat mengharapkan proses perilaku berubah ketika kita mengubah ukuran masalah. Tergantung pada algoritma, terjadi perubahan perilaku. Jadi, ini adalah salah satu hal paling penting yang harus kita perhatikan ketika kita mendesain suatu algoritma untuk beberapa masalah yang diberikan.

Ada berbagai notasi untuk mengukurnya dan yang paling penting adalah notasi Big O yang memberi Anda kompleksitas waktu kasus terburuk. Mungkin suatu saat kita akan membahas tentang notasi Big O.