Apa alasan untuk mempelajari berbagai algoritma / struktur data yang melayani tujuan yang sama?

Saya telah bertanya-tanya tentang pertanyaan ini sejak saya masih mahasiswa. Ini adalah pertanyaan umum tetapi saya akan menguraikan dengan contoh di bawah ini.

Saya telah melihat banyak algoritma - misalnya, untuk masalah aliran maksimum, saya tahu sekitar 3 algoritma yang dapat menyelesaikan masalah: Ford-Fulkerson, Edmonds-Karp & Dinic, dengan Dinic memiliki kompleksitas terbaik.

Untuk struktur data - misalnya, tumpukan - ada tumpukan biner, tumpukan binomial & tumpukan Fibonacci, dengan tumpukan Fibonacci memiliki kompleksitas keseluruhan terbaik.

Yang membuat saya bingung adalah: adakah alasan mengapa kita perlu mengetahui semuanya? Mengapa tidak belajar dan membiasakan diri dengan kompleksitas terbaik?

Saya tahu ini adalah yang terbaik jika kita tahu semuanya, saya hanya ingin tahu apakah ada alasan "lebih valid", seperti beberapa masalah / algoritma hanya dapat diselesaikan dengan menggunakan A tetapi tidak B , dll.

Ada buku teks yang menunggu untuk ditulis di beberapa titik, dengan judul yang berfungsi Struktur Data, Algoritma, dan Pengorbanan . Hampir setiap algoritma atau struktur data yang cenderung Anda pelajari di tingkat sarjana memiliki beberapa fitur yang membuatnya lebih baik untuk beberapa aplikasi daripada yang lain.

Mari kita ambil pengurutan sebagai contoh, karena semua orang terbiasa dengan algoritma pengurutan standar.

Pertama, kompleksitas bukan satu-satunya masalah. Dalam praktiknya, faktor konstan penting, itulah sebabnya (katakanlah) penyortiran cepat cenderung digunakan lebih dari penyortiran tumpukan meskipun penyortiran cepat memiliki kompleksitas kasus terburuk yang mengerikan.

Kedua, selalu ada kemungkinan Anda menemukan diri Anda dalam situasi di mana Anda memprogram di bawah kendala aneh. Saya pernah harus melakukan ekstraksi kuantil dari koleksi sampel berukuran (1000 atau lebih) sesegera mungkin, tetapi itu pada mikrokontroler kecil yang memiliki memori baca-tulis cadangan yang sangat sedikit, sehingga mengesampingkan sebagian besar mengurutkan algoritma. Shell sort adalah tradeoff terbaik, karena sub-kuadratik dan tidak memerlukan memori tambahan.$O(n \log n)$

Dalam kasus lain, gagasan dari algoritma atau struktur data mungkin berlaku untuk masalah tujuan khusus. Bubble sort sepertinya selalu lebih lambat dari pada insertion sort pada hardware yang sebenarnya, tetapi ide untuk melakukan bubble pass terkadang tepat seperti yang Anda butuhkan.

Pertimbangkan, misalnya, beberapa jenis visualisasi 3D atau permainan video pada kartu video modern, di mana Anda ingin menggambar objek secara berurutan, dari kamera terdekat ke kamera terjauh dari kamera untuk alasan kinerja, tetapi jika Anda tidak mendapatkan pesanan yang tepat, perangkat keras akan menanganinya. Jika Anda bergerak di sekitar lingkungan 3D, urutan relatif objek tidak akan banyak berubah di antara frame, jadi melakukan satu gelembung melewati setiap frame mungkin merupakan tradeoff yang masuk akal. (Mesin Sumber oleh Valve melakukan ini untuk efek partikel.)

Ada kegigihan, konkurensi, cache lokalitas, skalabilitas ke cluster / cloud, dan sejumlah alasan lain yang mungkin mengapa satu struktur data atau algoritma mungkin lebih tepat daripada yang lain bahkan diberikan kompleksitas komputasi yang sama untuk operasi yang Anda pedulikan.

Karena itu, itu tidak berarti bahwa Anda harus menghafal banyak algoritma dan struktur data untuk berjaga-jaga. Sebagian besar pertempuran menyadari bahwa ada tradeoff untuk dieksploitasi di tempat pertama, dan mengetahui ke mana harus mencari jika Anda berpikir mungkin ada sesuatu yang sesuai.

Selain dari fakta bahwa ada berjuta ukuran biaya (waktu berjalan, penggunaan memori, kesalahan cache, mispredictions cabang, kompleksitas implementasi, kelayakan verifikasi ...) pada berjuta model mesin (TM, RAM, PRAM, ...) , pertimbangan rata-rata-terburuk-kasus serta amortisasi untuk menimbang satu sama lain, sering ada juga perbedaan fungsional di luar ruang lingkup spesifikasi buku teks dasar.

Beberapa contoh:

• Mergesort stabil di mana Quicksort tidak.
• Pohon pencarian biner memberi Anda iterasi dalam urutan, hashtable tidak.
• Bellman-Ford dapat menangani bobot tepi negatif, Dijkstra tidak bisa.

Ada juga pertimbangan didaktik untuk dibuat:

• Seberapa mudah untuk memahami solusi yang lebih terlibat sebelum yang lebih sederhana? (Pohon AVL (dan analisisnya) tanpa BST; Dinic tanpa Ford-Fulkerson; ...)
• Apakah Anda melihat prinsip dan pola yang sama ketika Anda dihadapkan pada hanya satu solusi per masalah dibandingkan dengan terkena banyak solusi?
• Apakah paparan hanya satu solusi per masalah menyediakan pelatihan yang cukup (menuju penguasaan)?
• Haruskah Anda tahu luasnya solusi mana yang telah ditemukan (sehingga mencegah Anda menemukan kembali roda berulang kali¹)?
• Saat terpapar hanya satu solusi per masalah, apakah Anda akan memahami solusi lain yang Anda temukan di alam liar (misalnya, di perpustakaan pemrograman dunia nyata)?

1. Ini adalah sesuatu yang kita lihat banyak dari tipe programmer yang tidak memiliki kotak alat CS yang kaya.

Di dunia nyata , pada titik tertentu Anda mungkin bekerja pada perangkat lunak yang telah ditulis oleh tim orang lain. Beberapa perangkat lunak ini akan ditulis sebelum Anda dilahirkan!

Jadi untuk memahami algoritma / struktur data yang digunakan, akan sangat membantu untuk mengetahui sejumlah besar algoritma / struktur data, termasuk opsi yang tidak lagi dianggap "canggih".

Anda juga harus bekerja pada algoritma yang tidak standar dan hanya digunakan dalam aplikasi yang sedang Anda kerjakan. Ketika Anda harus meningkatkan algoritma ini, Anda akan menemukan bahwa otak Anda telah diisi dengan metode yang berguna untuk meningkatkan algoritma, karena Anda telah mempelajari bagaimana orang lain telah meningkatkan algoritma.

Inilah yang membuat seseorang yang telah mempelajari ilmu komputer berbeda dari seseorang yang baru belajar cara memprogram. Dalam sebagian besar pekerjaan yang telah saya kerjakan, ada waktu ketika mempelajari ilmu komputer saya bisa menyelesaikan masalah yang tidak bisa dipelajari oleh seorang programmer "belajar dari buku", tetapi 95% dari waktu saya menemukan bahwa mempelajari ilmu komputer tidak menguntungkan saya lebih dari programmer berpengalaman lainnya .

Banyak orang benar menyebutkan bahwa seringkali tidak ada satu algoritma terbaik - itu tergantung pada situasinya.

Ada juga kemungkinan bahwa suatu hari Anda akan menemukan situasi yang tidak dikenal. Semakin banyak algoritma yang Anda ketahui, semakin besar kemungkinan Anda akan tahu satu yang hampir merupakan solusi yang dapat Anda gunakan sebagai basis.

Banyak jawaban bagus, hanya sesuatu yang saya pikir tidak ada, meskipun jawaban Raphael agak menyebutkan ini.

Kemudahan implementasi juga sesuatu yang perlu dipertimbangkan.
Itu biasanya bukan masalah dengan algoritma pengurutan, karena sebagian besar platform / bahasa sudah memiliki satu implementasi (dan seringkali lebih baik daripada apa yang dapat Anda lakukan), tetapi lebih banyak algoritma yang tidak biasa mungkin tidak tersedia.
Tergantung pada masalah Anda, Anda mungkin tidak perlu algoritma terbaik mutlak jika waktu implementasi adalah 1 hari dibandingkan 2 minggu.