 |
| image by google |
Mengapa tidak efisien?
Tidak ada cara yang lebih baik untuk menjadi seorang desainer algoritma yang lebih baik daripada memiliki pemahaman yang mendalam dan penghargaan untuk algoritma.Katakanlah array Anda memiliki 50.000 entri, dan Anda brute-force pencarian (yaitu, pencarian dengan iterasi array penuh). Entri Anda sedang mencari, dalam skenario kasus terbaik, akan menjadi entri pertama dalam array 50.000-entry. Dalam skenario kasus terburuk, bagaimanapun, algoritma akan mengambil 50.000 kali lebih lama untuk selesai dari dalam skenario kasus terbaik.
Jadi apa yang lebih baik?
Sebaliknya, Anda akan mencari menggunakan pencarian biner. Ini melibatkan menyortir array (yang saya akan membiarkan Anda belajar tentang Anda sendiri) dan kemudian membagi array dalam setengah, dan memeriksa untuk melihat apakah jumlah pencari lebih besar atau lebih kecil dari tanda setengah dalam array. Jika lebih besar dari tanda setengah dari array diurutkan, maka kita tahu bahwa paruh pertama dapat dibuang, karena jumlah dicari bukan merupakan bagian dari array. Kami juga dapat memotong banyak pekerjaan dengan mendefinisikan batas-batas luar array dan memeriksa untuk melihat apakah jumlah dicari ada di luar mereka batas, dan jika demikian, kita telah mengambil apa yang akan menjadi operasi multi-iterasi dan mengubahnya menjadi operasi iterasi tunggal (yang dalam algoritma brute-force akan mengambil 50.000 operasi).
sortedHaystack = recursiveSort(haystack);
function bSearch(needle, sortedHaystack, firstIteration){
if (firstIteration){
if (needle > sortedHaystack.last || needle < sortedHaystack.first){
return false;
}
}
if (haystack.length == 2){
if (needle == haystack[0]) {
return haystack[0];
} else {
return haystack[1];
}
}
if (needle < haystack[haystack.length/2]){
bSearch(needle, haystack[0..haystack.length/2 -1], false);
} else {
bSearch(needle, haystack[haystack.length/2..haystack.length], false);
}
} Kedengarannya Cukup rumit
Mengambil sifat yang tampaknya rumit dari algoritma pencarian tunggal biner, dan menerapkannya ke miliaran link mungkin (seperti mencari melalui Google). Di luar itu, mari kita terapkan semacam sistem peringkat untuk penelusuran terkait untuk memberikan perintah dari halaman respon. Lebih baik lagi, menerapkan beberapa jenis yang tampaknya acak sistem "saran" berdasarkan model sosial kecerdasan buatan yang dirancang untuk mengidentifikasi siapa Anda mungkin ingin menambahkan sebagai teman.
Ini memberi kita pemahaman yang lebih jelas tentang mengapa algoritma yang lebih dari sekedar sebuah nama indah untuk fungsi. Pada terbaik mereka, mereka pintar, cara yang efisien untuk melakukan sesuatu yang membutuhkan tingkat yang lebih tinggi dari intuisi daripada solusi yang paling jelas. Mereka dapat mengambil apa yang mungkin akan membutuhkan superkomputer tahun untuk melakukan dan mengubahnya menjadi tugas yang selesai dalam hitungan detik pada ponsel.
baca terusannya artikel ini di Memahami Prinsip Desain Algoritma part 3
Memahami Prinsip Desain Algoritma part 2
4/
5
Oleh
Rudi
