DAA - Analisis Algoritma
Dalam analisis teoritis algoritme, adalah umum untuk memperkirakan kompleksitasnya dalam pengertian asimtotik, yaitu, untuk memperkirakan fungsi kompleksitas untuk input besar yang sewenang-wenang. Syarat"analysis of algorithms" diciptakan oleh Donald Knuth.
Analisis algoritme adalah bagian penting dari teori kompleksitas komputasi, yang memberikan estimasi teoretis untuk sumber daya yang diperlukan dari suatu algoritme untuk memecahkan masalah komputasi tertentu. Sebagian besar algoritme dirancang untuk bekerja dengan input dengan panjang sembarang. Analisis algoritma adalah penentuan jumlah waktu dan sumber daya ruang yang dibutuhkan untuk mengeksekusinya.
Biasanya, efisiensi atau waktu berjalan suatu algoritma dinyatakan sebagai fungsi yang menghubungkan panjang input dengan jumlah langkah yang disebut time complexity, atau volume memori, yang dikenal sebagai space complexity.
Kebutuhan Analisis
Pada bab ini, kita akan membahas perlunya analisis algoritma dan bagaimana memilih algoritma yang lebih baik untuk masalah tertentu karena satu masalah komputasi dapat diselesaikan dengan algoritma yang berbeda.
Dengan mempertimbangkan suatu algoritma untuk suatu masalah tertentu, kita dapat mulai mengembangkan pengenalan pola sehingga jenis masalah yang serupa dapat diselesaikan dengan bantuan algoritma ini.
Algoritme seringkali sangat berbeda satu sama lain, meskipun tujuan dari algoritme ini sama. Misalnya, kita tahu bahwa sekumpulan angka dapat diurutkan menggunakan algoritme yang berbeda. Jumlah perbandingan yang dilakukan oleh satu algoritme mungkin berbeda dengan algoritme lainnya untuk input yang sama. Karenanya, kompleksitas waktu dari algoritme tersebut mungkin berbeda. Pada saat yang sama, kita perlu menghitung ruang memori yang dibutuhkan oleh setiap algoritma.
Analisis algoritma adalah proses menganalisis kemampuan pemecahan masalah dari algoritma dalam hal waktu dan ukuran yang dibutuhkan (ukuran memori untuk penyimpanan selama implementasi). Namun, perhatian utama dari analisis algoritma adalah waktu atau kinerja yang dibutuhkan. Umumnya, kami melakukan jenis analisis berikut -
Worst-case - Jumlah langkah maksimum yang diambil pada setiap contoh ukuran a.
Best-case - Jumlah langkah minimum yang diambil pada setiap contoh ukuran a.
Average case - Jumlah rata-rata langkah yang diambil pada setiap contoh ukuran a.
Amortized - Urutan operasi yang diterapkan ke input ukuran a dirata-rata dari waktu ke waktu.
Untuk memecahkan masalah, kita perlu mempertimbangkan waktu serta kompleksitas ruang karena program dapat berjalan pada sistem di mana memori terbatas tetapi tersedia ruang yang memadai atau mungkin sebaliknya. Dalam konteks ini, jika kita membandingkanbubble sort dan merge sort. Jenis gelembung tidak memerlukan memori tambahan, tetapi jenis penggabungan memerlukan ruang tambahan. Meskipun kompleksitas waktu jenis gelembung lebih tinggi dibandingkan dengan jenis gabungan, kita mungkin perlu menerapkan jenis gelembung jika program perlu dijalankan di lingkungan, di mana memori sangat terbatas.