Saya telah mencari kursus online yang bagus dalam struktur data tetapi telah menemukan bahwa Google juga mengembalikan hasil untuk kursus algoritma, yang mengatakan hal-hal seperti:
Dalam kursus ini Anda akan mempelajari beberapa prinsip dasar desain algoritma: metode divide-and-conquer, algoritma grafik, struktur data praktis (heaps, tabel hash, pohon pencarian) , algoritma acak, dan banyak lagi. [sumber]
dan
Pada akhir kelas ini Anda akan memahami konsep-konsep kunci yang diperlukan untuk menyusun algoritma baru untuk grafik dan struktur data penting lainnya dan untuk mengevaluasi efisiensi dari algoritma ini. [sumber]
dan
Kursus ini memberikan pengantar untuk pemodelan matematika masalah komputasi. Ini mencakup algoritma umum, paradigma algoritmik, dan struktur data yang digunakan untuk menyelesaikan masalah ini . [sumber]
Pertanyaan saya adalah: apakah algoritma dan struktur data terkait erat, artinya semuanya harus dipahami bersama atau apakah satu topik lebih mendasar daripada yang lain?
EDIT: Bagi mereka yang memberikan suara untuk menutup pertanyaan ini, dapatkah Anda memberi tahu saya alasannya dan bagaimana cara meningkatkan yang ini? Belajar mengajukan pertanyaan yang tepat adalah bagian dari proses pendidikan.
if less than recurse to the left; if greater than, recurse to the right; if equal, returnpencarian naif atau yang sedikit lebih canggihif less than recurse to the left; otherwise keep track of this value as a potential candidate and recurse to the right; check for equality once we reach the leaves. Mereka memiliki jumlah perbandingan yang sedikit berbeda. Keduanya adalah salah satu dari banyak hal yang dapat Anda pilih untuk dilakukan dengan pohon.Jawaban:
Segala macam campuran memang ada. Anda memiliki struktur data, yang tidak terkait dengan algoritma, algoritma, yang tidak memerlukan struktur data (nyata), tetapi paling sering keduanya datang dalam satu paket.
Sunting: seperti yang ditunjukkan @Doval dengan benar, struktur data per se tidak memiliki operasi apa pun yang terkait dengannya. Tindakan menggabungkan struktur data dan algoritma membentuk tipe data abstrak.
Struktur data tanpa algoritma
Pertimbangkan misalnya struktur data untuk menyimpan koordinat 2 dimensi, yang disebut dengan tepat
Point. Tidak ada banyak dalam hal algoritma yang harus dilakukan untuk suatu titik dan itu benar-benar hanya sebuah wadah untuk suatuxdanynilai. Tentu saja, dengan memberikan struktur data ini, Anda sekarang dapat menambahkan semua jenis algoritma di atasnya (perhitungan jarak, lambung cembung, apa pun yang Anda miliki).Anda dapat memikirkan banyak struktur data, yang hanya merupakan akumulasi dari data individual. Meskipun hal ini sering terjadi dalam praktik, mereka tidak menghasilkan bahan pengajaran yang baik, karena tidak ada yang dapat dipelajari darinya, setelah Anda mengerti, bahwa item data tunggal dapat diakumulasikan ke dalam struktur data baru (seperti apa yang Anda pelajari setelah
Pointcontoh di atas , jika saya memberi Anda struktur data yang luar biasa yang disebutPoint3D, yang dapat melakukan hal yang sama untuk ruang 3-dimensi?)Algoritma tanpa struktur data (nyata)
"Nyata", karena jelas setiap algoritma yang menarik membutuhkan tipe data primitif seperti bilangan bulat atau boolean, dan kami tidak ingin menganggapnya sebagai struktur data dalam konteks ini. Demikian pula untuk di atas, algoritma ini biasanya agak sederhana. Secara khusus, mereka tidak datang dengan keadaan rumit apa pun, karena itu biasanya masuk ke dalam struktur data (lihat bagian selanjutnya).
Contoh untuk algoritma seperti itu akan menghitung pembagi umum terbesar dari dua angka. Algoritma Euklid untuk gcd benar-benar hanya perlu menampung dua bilangan bulat dan memanipulasinya.
Begitu semuanya mulai menjadi lebih menarik, Anda segera memasuki dunia tipe data abstrak. Misalnya, ayakan Eratosthenes didasarkan pada array. Kita bisa berdiskusi sekarang, apakah array masih primitif, atau bahkan, Anda bisa mendiskusikan jika integer belum menjadi struktur data. Either way, algoritma yang ada sepenuhnya tanpa struktur data agak membosankan, bahkan jika Anda menerima keberadaannya yang terisolasi.
Algoritma dikombinasikan dengan struktur data, alias tipe data abstrak
Sekarang ini yang menarik, tetapi karena dua alasan yang sangat berbeda. Biasanya, Anda dapat mendekati ini dari dua arah: struktur data terlebih dahulu, atau algoritma terlebih dahulu.
Sementara tipe data abstrak didefinisikan oleh kombinasi struktur data + algoritma / operasi, kita sering melihatnya dengan fokus pada salah satu dari mereka dan menganggap yang lain sebagai enabler.
Struktur data, lalu algoritma
Anda akan menemukan tipe data abstrak, yang agak mudah digunakan, tetapi melibatkan algoritma yang lebih atau kurang rumit untuk membuatnya bekerja secara internal. Sebagai contoh, sebuah
HashMapsepele untuk digunakan, tetapi melibatkan fungsi hash yang bagus dan berurusan dengan tabrakan hash di dalam. Namun, dari sudut pandang Anda sebagai pengguna, Anda peduli tentang hal itu sebagai sesuatu yang menyimpan data untuk Anda, bukan sesuatu yang melakukan sesuatu untuk Anda.Berbeda dengan grup terakhir di bawah ini, struktur data ini tidak mengekspos penggunanya terhadap algoritma ini. Anda tidak perlu tahu, atau peduli, tentang
HashMapfungsi hash internal agar dapat menggunakannya. (Namun, untuk menggunakannya secara efektif, Anda mungkin ingin mengetahui hal-hal ini;)Algoritma, lalu struktur data
Arah yang lain berarti Anda memiliki algoritme, yang Anda ingin dapat cukup gunakan, tetapi yang membutuhkan struktur data secara internal untuk membuatnya berfungsi sebagaimana dimaksud. Contohnya adalah algoritme pembagian ruang biner (BSP), yang dapat Anda minta 2-dimensi
Pointdari sekumpulan titik besar yang paling dekat dengan titik kueri yang diberikan. Namun, Anda memerlukan struktur pohon (dan bahkan algoritma tambahan seperti perhitungan jarak) di dalam untuk benar-benar menulis algoritma.Secara umum, dapat dikatakan bahwa algoritma dalam grup ini menggunakan struktur data yang terlibat untuk representasi keadaan internal mereka. Saya berpendapat, bahwa kelompok algoritma ini adalah yang paling beragam dan Anda akan menemukan banyak yang berbeda yang sesuai dengan skema umum ini. Mengenai sudut pandang, kami melihat ini sebagai menarik, karena mereka melakukan sesuatu (mis. Penyortiran) untuk kami, dan tidak terlalu peduli tentang bagian data holding.
Struktur dan algoritma data yang terkait erat
Akhirnya, Anda memiliki struktur data, yang sangat dekat terkait dengan algoritma yang berhubungan langsung dengan mereka. Contoh khas adalah pohon biner, yang, ketika Anda ingin melakukan sesuatu yang bermakna dengannya, memaksakan topik algoritma berjalan pohon pada Anda (kedalaman-pertama, luas-pertama, apa pun).
Untuk kasus ini, kami mengubah fokus pandangan kami tentang tipe data abstrak yang dihasilkan setiap begitu sering. Kadang-kadang Anda peduli tentang struktur pohon Anda, beberapa menit kemudian Anda peduli untuk dapat menjalankan operasi pencarian di atasnya, lalu Anda bertanya-tanya tentang menghapus sebuah simpul, dan segera tentang bagaimana struktur terlihat setelahnya. Walaupun semua ini berlaku untuk bagian lain di atas juga, itu bukan sesuatu yang menjadi fokus utama dalam pikiran Anda, misalnya, ketika Anda menyimpan / mengambil data ke / dari
Map, atau ketika Anda mengurutkan daftar yang ditautkan.sumber
Mapadalah tipe data abstrak yang dapat diimplementasikan menggunakan struktur data tertentu dan serangkaian algoritma yang menghasilkan hasil yang diinginkan dengan melintasi dan memanipulasi struktur. Struktur data tidak menyembunyikan algoritme, karena tidak memiliki algoritma; tipe data abstrak menyembunyikan struktur data (itulah yang membuatnya abstrak.)Struktur data sering mempengaruhi detail suatu algoritma. Karena itu keduanya sering berjalan beriringan.
Pertimbangkan misalnya sebuah algoritma untuk memotong rumput Anda. Bagaimana Anda memotong rumput Anda kemungkinan akan dipengaruhi oleh struktur aktual halaman Anda. Jika Anda tinggal di sebuah rumah kecil di pinggiran kota yang padat dan halaman Anda hanya persegi panjang kecil beberapa meter persegi, Anda mungkin akan lebih suka memotong rumput Anda dengan mesin dorong daripada mesin traktor / mesin pemotong. Jika halaman Anda melibatkan banyak acre lahan padang rumput datar, pilihan Anda mungkin untuk mesin pemotong berkuda sebagai lawan dari mesin pemotong dorong (meskipun salah satu mesin pemotong mungkin pada akhirnya akan menyelesaikan pekerjaan). Jika halaman Anda melibatkan hektar tanah dengan area datar yang luas, tetapi beberapa bukit kecil dan sejumlah pohon, Anda dapat mengembangkan algoritma yang lebih menarik untuk memotong halaman yang melibatkan mesin pemotong berkuda dan mesin pemotong dorong, atau rumput lainnya. teknik memotong.
Namun pada akhirnya, struktur data Anda mungkin memiliki dampak signifikan pada keputusan Anda tentang bagaimana mengembangkan algoritma Anda (atau algoritma mana yang digunakan). Karena alasan ini, kedua topik tersebut sering berjalan seiring.
Dan sebaliknya: kadang-kadang algoritma yang kita ingin gunakan pengaruh (setidaknya pada awal komputasi) struktur data yang Anda kembangkan untuk mendukung algoritma. Misalnya pergi dari daftar array ke gagasan daftar yang ditautkan dan akhirnya ke BST untuk menyimpan daftar yang dipesan yang akan memungkinkan untuk pencarian cepat.
sumber