Analisis algoritma

Dalam ilmu komputer, analisis algoritma adalah proses menemukan kompleksitas komputasional dari algoritma—jumlah waktu, penyimpanan, atau sumber daya lain yang dibutuhkan untuk mengeksekusinya. Biasanya, ini melibatkan penentuan fungsi yang menghubungkan ukuran masukan algoritma dengan jumlah langkah yang diambilnya (kompleksitas waktu) atau jumlah lokasi penyimpanan yang digunakannya (kompleksitas ruang). Suatu algoritma dikatakan efisien ketika nilai fungsi ini kecil, atau tumbuh lambat dibandingkan dengan pertumbuhan ukuran masukan. Masukan yang berbeda dengan ukuran yang sama dapat menyebabkan algoritma memiliki perilaku yang berbeda, sehingga deskripsi kasus terbaik, terburuk, dan rata-rata mungkin semuanya menarik secara praktis. Jika tidak ditentukan sebaliknya, fungsi yang menggambarkan kinerja suatu algoritma biasanya merupakan batas atas, yang ditentukan dari masukan kasus terburuk ke algoritma.

Untuk mencari entri tertentu dalam daftar terurut tertentu, baik algoritma pencarian biner maupun linear (yang mengabaikan urutan) dapat digunakan. Analisis algoritma pertama dan kedua menunjukkan bahwa algoritma tersebut membutuhkan paling banyak log₂ n dan n periksa langkah-langkahnya, masing-masing, untuk daftar ukuran n. Dalam contoh daftar ukuran 33 yang digambarkan, pencarian "Morin, Arthur" membutuhkan 5 dan 28 langkah dengan biner (ditunjukkan dalam sian) dan linier (magenta) pencarian, masing-masing.

Grafik fungsi yang umum digunakan dalam analisis algoritma, menunjukkan jumlah operasi N versus ukuran masukan n untuk setiap fungsi

Istilah "analisis algoritma" dicetuskan oleh Donald Knuth.^[1] Analisis algoritma merupakan bagian penting dari teori kompleksitas komputasional yang lebih luas, yang menyediakan estimasi teoritis untuk sumber daya yang dibutuhkan oleh algoritma apa pun yang memecahkan masalah komputasional tertentu. Estimasi ini memberikan wawasan tentang arah pencarian yang wajar untuk algoritma yang efisien.

Dalam analisis teoritis algoritma, biasanya kompleksitas diestimasi dalam pengertian asimtotik, yaitu, untuk menaksir fungsi kompleksitas untuk input yang besarnya sembarang. Notasi Big O, Notasi Big Omega, dan Notasi Big Theta digunakan untuk tujuan ini.^[2] Misalnya, pencarian biner dikatakan berjalan dalam sejumlah langkah yang sebanding dengan logaritma ukuran n dari daftar yang diurutkan yang sedang dicari, atau di O(log n), secara umum "dalam waktu logaritmik". Biasanya estimasi asimptotik digunakan karena implementasi yang berbeda dari algoritma yang sama mungkin berbeda dalam efisiensinya. Namun efisiensi dari dua implementasi "wajar" dari algoritma tertentu terkait dengan faktor perkalian konstan yang disebut konstanta tersembunyi.

Pengukuran efisiensi yang tepat (tidak asimtotik) terkadang dapat dihitung, tetapi biasanya memerlukan asumsi tertentu mengenai implementasi algoritma tertentu, yang disebut model komputasi. Model komputasi dapat didefinisikan dalam istilah komputer abstrak, misalnya mesin Turing, dan/atau dengan mendalilkan bahwa operasi tertentu dieksekusi dalam satuan waktu. ... Bagi sebagian orang (misalnya programmer game),