Algoritme
Sangat penting untuk mengetahui berapa banyak sumber tertentu (seperti waktu dan tempat penyimpanan) secara teoretis diperlukan untuk sebuah algoritme. Metode-metode telah dikembangkan untuk analisis algoritme untuk mendapatkan jawaban kuantitatif (estimasi); sebagai contohnya, algoritme pengurutan di atas memerlukan waktu O (n), menggunakan notasi O besar dengan n sebagai panjang deret (yang
akan diurut). Setiap saat algoritme hanya perlu mengingat dua nilai: nilai terbesar yang ditemukan, dan posisinya sekarang dideretan input. Oleh karena itu dikatakan memiliki kebutuhan ruang O (1), jika ruang yang dibutuhkan untuk menyimpan angka masukan tidak dihitung, atau O (n) jika dihitung.
Algoritme berbeda mungkin menyelesaikan pekerjaan yang sama dengan kumpulan instruksi yang berbeda dengan waktu, ruang, atau 'usaha' lebih sedikit atau banyak dari yang lain. Sebagai contohnya, algoritme pencairan binari biasanya mengungguli pencarian berderet secara paksa bila digunakan untuk tabel pencarian pada deret terurut.
Analisis dan kajian algoritme adalah bidang dari ilmu komputer, dan biasanya dilakukan secara abstrak tanpa menggunakan bahasa pemrograman tertentu atau implementasi. Dalam artian, analisis algoritme mirip dengan bidang matematika lainnya yang mana fokus pada properti yang mendasari algoritme dan bukan pada implementasi tertentu. Biasanya pseudokode digunakan pada analisis karena merupakan representasi paling
umum dan sederhana. Namun, pada akhirnya, kebanyakan algoritme diimplementasikan di perangkat keras/lunak tertentu dan efisiensi algoritmik mereka akhirnya diuji menggunakan kode yang sebenarnya. Untuk solusi dari sebuah masalah, efisiensi dari algoritme tertentu mungkin tidak terlalu berpengaruh (kecuali n sangat besar) tetapi bagi algoritme yang dirancang
untuk kecepatan interaktif, komersial, atau penggunaan ilmiah jangka panjang ia bisa saja kritikal. Meningkatkan n dari kecil ke n yang besar biasanya menunjukan ketak efisienan algoritme yang tidak berbahaya.
Pengujian empiris berguna karena bisa membuka interaksi tak terduga yang mempengaruhi performa. Benchmark bisa digunakan untuk membandingkan potensi kenaikan sebelum/sesudah algoritme setelah optimisasi program dilakukan.
Untuk menggambarkan kemungkinan potensi peningkatan bahkan pada algoritme yang sudah teruji, inovasi terbaru, berkaitan dengan algoritme FFT (banyak digunakan di bidang pemrosesan gambar), bisa menurunkan waktu pemrosesan dengan faktor sampai 1000 untuk aplikasi seperti pencitraan medis. Secara umum, peningkatan kecepatan bergantung pada properti khusus dari permasalahan, yang mana sangat umum pada
aplikasi praktis. Percepatan dengan tingkat seperti itu membolehkan perangkat komputasi yang sering menggunakan pemrosesan gambar (seperti kamera digital dan peralatan medis) menghabiskan daya yang lebih sedikit.
Rekursi atau iterasi Sebuah algoritme rekursi yaitu algoritme yang memanggil dirinya sendiri berulang kali sampai kondisi tertentu tercapai, ini merupakan metode umum bagi pemrograman fungsional. Algoritme iteratif menggunakan konstruksi berulang seperti pengulangan dan terkadang struktur data tambahan seperti tumpukan untuk menyelesaikan permasalahan. Beberapa permasalahan secara alami cocok dengan satu
implementasi atau lainnya. Sebagai contoh, Menara Hanoi dikenal dengan implementasi rekursif. Setiap versi rekursif memiliki kesamaan (tapi bisa lebih atau kurang kompleks) dengan versi iteratif, dan sebaliknya.
Logical Sebuah algoritme bisa dilihat sebagai logika deduksi terkontrol. Pernyataan ini diekspresikan sebagai: Algoritme = logika + kontrol. Komponen logika mengekspresikan aksioma yang bisa digunakan dalam komputasi dan komponen kontrol menentukan cara deduksi digunakan pada aksioma. Ini merupakan dasar dari paradigma pemrograman logika. Dalam bahasa pemrograman logika murni komponen
kontrol adalah tetap dan algoritme ditentukan dengan memberikan hanya komponen logikanya. Daya tarik dari pendekatan ini adalah semantik elegan: sebuah perubahan dalam aksioma memiliki perubahan dalam algoritme.
Serial, paralel atau terdistribusi Algoritme biasanya dibicarakan dengan asumsi bahwa komputer menjalankan satu instruksi algoritme setiap waktu. Komputer tersebut terkadang disebut dengan komputer serial. Rancangan algoritme untuk lingkungan tersebut disebut dengan algoritme serial, terbalik dengan algoritme paralel atau algoritme terdistribusi. Algoritme paralel memanfaatkan arsitektur komputer yang mana beberapa prosesor bisa mengerjakan
masalah di waktu yang sama, selain itu algoritme terdistribusi memanfaatkan banyak mesin yang terhubung dengan jaringan. Algoritme paralel atau terdistribusi membagi permasalahan menjadi banyak sub-masalah simetris atau asimetris dan mengumpulkan hasilnya kembali. Konsumsi sumber pada algoritme tersebut tidak hanya perputaran prosesor disetiap prosesor tetapi juga daya komunikasi antara
prosesor. Algoritme pengurutan bisa diparalelkan secara efisien, tetapi biaya komunikasinya sangat mahal. Algoritme iteratif secara umum bisa diparalelkan. Beberapa permasalahan tidak ada algoritme paralelnya, dan disebut dengan permasalahan serial lahiriah.
Deterministik atau non-deterministik Algoritme deterministik menyelesaikan masalah dengan keputusan yang tepat disetiap langkah dari algoritme sedangkan algoritme non-deterministik menyelesaikan masalah lewat penerkaan walaupun penerkaan biasanya lebih akurat dengan menggunakan heuristik.
Tepat atau perkiraan Bila banyak algoritme sampai pada solusi yang tepat, algoritme perkiraan mencari sebuah perkiraan yang terdekat dengan solusi benarnya. Perkiraan bisa menggunakan baik strategi deterministik atau acak. Algoritme seperti itu memiliki nilai guna untuk banyak permasalahan sulit.
Algoritme quantum Berjalan di model realistik dari komputasi quantum. Istilah ini biasanya digunakan untuk algoritme yang tampak pada dasarnya quantum, atau menggunakan beberapa fitur penting komputasi quantum seperti superposisi quantum atau belitan quantum.
Cara lain mengklasifikasikan algoritme adalah dengan metodologi rancangannya atau paradigma. Ada sejumlah paradigma, tiap-tiapnya berbeda dari yang lain. Lebih lanjut, setiap kategori tersebut mengikutkan banyak tipe algoritme yang berbeda. Beberapa paradigma umum termasuk:
Pencarian paksa atau pencarian mendalam Ini merupakan metode naif mencoba setiap kemungkinan solusi untuk melihat yang terbaik.
Membagi dan menaklukan (Divide and conqueror) Algoritme bagi dan takluk secara berulang mereduksi instansi jumlah masalah menjadi satu atau lebih kecil instasi masalah yang sama (biasanya secara rekursif) sampai instansi cukup kecil diselesaikan dengan mudah. Salah satu contoh bagi dan takluk adalah pengurutan gabung. Pengurutan dapat dilakukan disetiap segmen data setelah
membagi data menjadi segmen-segmen dan urutan seluruh data bisa didapat pada fase takluk dengan menggabungkan segmen-segmen. Variasi sederhana dari bagi-dan-takluk disebut algoritme kurang dan takluk, yang menyelesaikan sub-masalah yang sama dan menggunakan solusi dari sub-masalah tersebut untuk menyelesaikan masalah yang lebih besar. Bagi dan takluk
membagi permasalahan menjadi banyak sub-masalah dan sehingga tahap takluk lebih kompleks daripada algoritme kurang-dan-taklukan. Sebuah contoh dari algoritme kurang-dan-taklukan adalah algoritme pencarian binari.
Pencarian dan enumerasi Banyak masalah (seperti bermain catur) bisa dimodelkan sebagai masalah dalam grafik. Sebuah algoritme eksplorasi grafik menentukan aturan-aturan untuk bergerak disekitar grafik dan berguna bagi masalah tersebut. Kategori ini juga mengikutkan algoritme pencarian, enumerasi batas dan cabang dan backtracking.