Dalam artikel ini, kita akan berbicara tentang mengapa algoritma dan analisisnya penting. Saat menganalisis algoritma, fokus umumnya pada penggunaan CPU (waktu), penggunaan Memori, penggunaan Disk, dan penggunaan Jaringan. Semua itu penting, tetapi yang paling dikhawatirkan adalah waktu CPU. Perhatikan perbedaan antara:
Performa: Berapa banyak waktu/memori/disk/etc. yang digunakan saat menjalankan program. Ini tergantung pada mesin, kompiler, dll., serta kode yang kita tulis.
Kompleksitas: Bagaimana kebutuhan sumber daya dari program atau algoritma berkembang, yaitu apa yang terjadi saat ukuran masalah yang dipecahkan oleh kode semakin besar.
Catatan: Kompleksitas mempengaruhi performa, tetapi tidak sebaliknya.
Analisis Algoritma: Analisis algoritma adalah bagian penting dari teori kompleksitas komputasi, yang memberikan perkiraan teoritis untuk sumber daya yang diperlukan oleh algoritma untuk memecahkan masalah komputasi tertentu. Analisis algoritma adalah penentuan jumlah sumber daya waktu dan ruang yang diperlukan untuk menjalankannya.
Mengapa Analisis Algoritma Penting?
- Untuk memprediksi perilaku suatu algoritma tanpa mengimplementasikannya di komputer tertentu.
- Lebih nyaman memiliki ukuran sederhana untuk efisiensi algoritma daripada mengimplementasikan algoritma dan menguji efisiensinya setiap kali parameter tertentu dalam sistem komputer dasar berubah.
- Tidak mungkin memprediksi perilaku yang tepat dari suatu algoritma. Terlalu banyak faktor yang mempengaruhi.
- Analisis ini hanya pendekatan; tidak sempurna.
- Yang lebih penting, dengan menganalisis berbagai algoritma, kita dapat membandingkannya untuk menentukan yang terbaik untuk tujuan kita.
Jenis Analisis Algoritma:
- Kasus Terbaik
- Kasus Terburuk
- Kasus Rata-rata
Kasus Terbaik: Tentukan masukan di mana algoritma memerlukan waktu lebih sedikit atau waktu minimum. Di kasus terbaik, hitung batas bawah algoritma. Contoh: Pencarian linear saat data pencarian ada di lokasi pertama data besar, maka kasus terbaik terjadi.
Kasus Terburuk: Tentukan masukan di mana algoritma memerlukan waktu lama atau waktu maksimum. Di kasus terburuk, hitung batas atas algoritma. Contoh: Pencarian linear saat data pencarian sama sekali tidak ada, maka kasus terburuk terjadi.
Kasus Rata-rata: Dalam kasus rata-rata, ambil semua masukan acak dan hitung waktu komputasi untuk semua masukan tersebut. Lalu bagi dengan total jumlah masukan.
Kasus Rata-rata = waktu semua kasus acak / total jumlah kasus