Sepuluh algoritma praktikal asas yang mesti diketahui oleh pengaturcara dan penjelasannya

• ### Algoritma 1: Algoritma Urutan Cepat

Pengurutan pantas adalah satu algoritma pengurutan yang dibangunkan oleh Tony Hall. Dalam keadaan biasa, pengurutan n item memerlukan O (nlogn) kali perbandingan. Dalam keadaan terburuk, ia memerlukan O (n2) kali perbandingan, tetapi keadaan ini tidak biasa. Sebenarnya, pengurutan pantas biasanya lebih cepat daripada algoritma lain, kerana lingkaran dalamannya (innerloop) dapat dilaksanakan dengan sangat cekap pada kebanyakan seni bina.

Urutan pantas menggunakan strategi Divideandconquer untuk membahagikan senarai bersiri menjadi dua sub-senarai bersiri.

Langkah algoritma:

• 1 , pilih satu elemen dari susunan, yang dikenali sebagai pivot (pivot),

• 1. Susun semula nombor, semua elemen yang lebih kecil daripada nilai asas diletakkan di hadapan asas, dan semua elemen yang lebih besar daripada nilai asas diletakkan di belakang asas (dengan bilangan yang sama boleh pergi ke mana-mana sisi). Selepas keluar dari bahagian ini, asas itu berada di tengah-tengah nombor.
• 1. Recursively ((recursive) mengurutkan sub-angka yang lebih kecil daripada unsur asas dan sub-angka yang lebih besar daripada unsur asas.

  Keadaan paling asas untuk pengulangan ialah saiz nombor adalah sifar atau satu, yang bermaksud bahawa ia telah disusun dengan baik selama-lamanya. Walaupun terus berundur, algoritma ini akan selalu keluar, kerana dalam setiap iterasi, ia akan meletakkan sekurang-kurangnya satu elemen ke tempat terakhirnya.

• ### Algoritma 2: Algoritma pengurutan tumpukan

Heapsort ialah satu jenis algoritma pengaturcaraan yang direka menggunakan struktur data seperti heapsort. Heapsort adalah struktur yang hampir sama dengan pokok binari yang sempurna, dan pada masa yang sama memenuhi sifat pengumpulan: nilai kunci atau indeks subnode selalu lebih kecil daripada (atau lebih besar daripada) nod induknya.

Kompleksiti masa purata untuk susun atur tumpukan adalah O ((nlogn) 。

Langkah algoritma:

• 1 , mencipta satu tumpukan H[0..n-1]

• 2, menukarkan kepala (maksimum) dan hujung

• 1. Kurangkan saiz tumpukan menjadi 1, dan panggil shift_down ((0)), untuk menyesuaikan data di bahagian atas tab baru ke kedudukan yang sesuai

• 4, Ulangi langkah 2 sehingga saiz tumpukan adalah 1

• Algoritma 3: Penggabungan dan Pengurutan

Mergesort ialah satu algoritma pengurutan yang berkesan berdasarkan operasi penggabungan. Algoritma ini merupakan aplikasi yang sangat tipikal menggunakan DivideandConquer.

Langkah algoritma:

• 1. Ruang permohonan, dengan saiznya sebagai jumlah dua urutan yang telah disusun, ruang ini digunakan untuk menyimpan urutan gabungan
• 1. Tetapkan dua penunjuk, masing-masing sebagai permulaan dua urutan yang telah diurutkan
• 1. Bandingkan dua elemen yang diarahkan oleh penunjuk, pilih elemen yang lebih kecil untuk dimasukkan ke dalam ruang gabungan, dan gerakkan penunjuk ke kedudukan seterusnya
• 1. Ulangi langkah 3 sehingga satu penunjuk mencapai akhir urutan
• 1. Salin semua elemen yang tinggal dari urutan lain secara langsung ke hujung urutan gabungan

• Algoritma 4: Algoritma carian dua

Algoritma carian duaan adalah algoritma carian untuk mencari elemen tertentu dalam array tersusun. Proses carian bermula dari elemen tengah dalam array, dan proses carian berakhir jika elemen tengah adalah elemen yang dicari; jika elemen tertentu lebih besar atau lebih kecil daripada elemen tengah, carian bermula pada separuh dari array yang lebih besar atau lebih kecil daripada elemen tengah, dan perbandingan bermula dari elemen tengah seperti yang dimulakan. Jika pada langkah tertentu nombor langkahnya kosong, maka ia tidak dapat dijumpai.

• ### Algoritma lima: BFPRT (algoritma carian linear)

Masalah yang diselesaikan oleh algoritma BFPRT adalah sangat klasik, iaitu memilih elemen k terbesar (k kecil) dari urutan n elemen, melalui analisis yang bijak, BFPRT dapat menjamin kerumitan masa linear dalam keadaan terburuk. Pemikiran algoritma ini serupa dengan pemikiran urutan cepat, tentu saja, untuk menjadikan algoritma dalam keadaan terburuk, masih dapat mencapai kerumitan masa o (n), lima pengarang algoritma telah melakukan pengendalian yang baik.

Langkah algoritma:

• 1 , bagi n unsur setiap 5 satu kumpulan, ke dalam n/5 (perbatasan atas) kumpulan.

• 1. Keluarkan digit tengah bagi setiap kumpulan, dan pilih cara untuk menyusunnya, seperti menyisipkan.
• 1. Algoritma pemilihan panggilan berulang mencari median semua median dalam langkah sebelumnya, ditetapkan sebagai x, dan dipilih sebagai yang kecil di tengah jika ada beberapa median.
• 1. Bagi membahagikan array dengan x, letakkan bilangan yang lebih kecil daripada dan sama dengan x ialah k, dan bilangan yang lebih besar daripada x ialah n-k.

• 5, jika i==k, kembalikan x; jika ik, berulang mencari elemen ke-i-k yang lebih kecil daripada elemen yang lebih besar daripada x.

  Keadaan penamatan: apabila n = 1, yang dikembalikan ialah elemen kecil i.

• Algoritma 6: DFS (pencarian keutamaan kedalaman)

Deep-First-Search, adalah sejenis algoritma pencarian. Ia mengembara sepanjang kedalaman pokok ke nod pokok dan mencari cabang pokok yang paling dalam. Apabila semua sisi nod v telah dijelajahi, pencarian akan kembali ke nod permulaan di sisi yang menemui nod v. Proses ini berterusan sehingga semua nod dapat dicapai dari nod sumber yang telah dijumpai.

Pencarian keutamaan kedalaman adalah algoritma klasik dalam grafologi, menggunakan algoritma pencarian keutamaan kedalaman boleh menghasilkan jadual penyaringan topologi yang sesuai dengan graf sasaran, menggunakan jadual penyaringan topologi boleh menyelesaikan banyak masalah grafologi yang berkaitan, seperti masalah laluan maksimum dan sebagainya.

Langkah-langkah algoritma keutamaan dalaman:

• 1 , lawatan ke puncak v;

• 2 . Bermula dari titik-titik yang berdekatan dengan v yang tidak dikunjungi, melakukan perjalanan ke dalam grafik dengan keutamaan; sehingga puncak yang mempunyai laluan yang sama dengan v di dalam grafik dikunjungi;

• 1. Jika ada puncak yang masih belum dikunjungi dalam peta masa ini, mulakan dari puncak yang belum dikunjungi dan lakukan semula perjalanan keutamaan kedalaman sehingga semua puncak di peta telah dikunjungi.

  Ia mungkin lebih abstrak, sebagai contoh:

  DFS bermula dengan v, dan kemudian pergi ke mana-mana puncak yang berdekatan dengan w1; kemudian pergi ke puncak yang berdekatan dengan w1 tetapi belum dikunjungi oleh w2; dan kemudian pergi ke puncak yang berdekatan dengan w2 dan melakukan perjalanan yang sama, … dan seterusnya, sehingga semua puncak berdekatan telah dikunjungi oleh u.

  Kemudian, kembali ke puncak yang baru anda lawati pada kali sebelumnya dan lihat apakah ada puncak berdekatan yang belum anda lawati. Jika ada, lawati puncak itu dan kemudian mulakan dari puncak itu untuk melakukan kunjungan yang serupa dengan yang sebelumnya; jika tidak, kembali lagi untuk mencari. Ulangi proses di atas sehingga semua puncak dalam peta sambungan telah dikunjungi.

• Algoritma 7: BFS (Broad Foresight Prioritized Search)

Breadth-First-Search (BFS) adalah algoritma carian grafik. Secara ringkasnya, BFS adalah nod yang bermula dari nod akar dan berjalan di sepanjang lebar pokok. Algoritma ini dihentikan jika semua nod telah dikunjungi.

Langkah algoritma:

• Pertama, letakkan nod akar dalam barisan.

• 1. Keluarkan nod pertama dari barisan dan periksa sama ada ia adalah sasaran.

  Jika sasaran ditemui, hentikan pencarian dan maklumkan hasilnya. Jika tidak, masukkan semua subnode langsung yang belum diperiksa ke dalam barisan.

• 3 , Jika barisan kosong, bermakna keseluruhan peta telah diperiksa oleh yang lain atau tidak ada sasaran yang ingin dicari dalam peta. Akhir carian dan penghantar kembali tidak dapat mencari sasaran yang lain.

• 1. Ulangi langkah 2.

• Algoritma 8: Algoritma Dijkstra

Algoritma Dykstra (Bahasa Inggeris: Dykstra-salgorithm) dikemukakan oleh saintis komputer Belanda, Ezhel Dykstra. Algoritma Dykstra menggunakan pencarian keutamaan luas untuk menyelesaikan masalah laluan terpendek sumber tunggal untuk grafik berorientasikan bukan negatif. Algoritma ini sering digunakan dalam algoritma laluan atau sebagai sub-modul untuk algoritma grafik lain.

Input algoritma ini mengandungi satu graf berorientasikan dengan berat G, dan satu puncak sumber dalam G S. Kita mewakili kumpulan semua puncak dalam G dengan V. Setiap sisi dalam graf adalah pasangan elemen berurutan yang dibentuk oleh dua puncak.[[0,∞] definisi.

Oleh itu, w(u,v) adalah berat bukan negatif dari puncak u ke puncak v (w) ⋅ weight of the side can be imagined as the distance between two peaks ⋅ the weight of the path between any two points is the sum of the weights of all the sides on that path ⋅ it is known that V mempunyai puncak s dan t, Dijkstra’s algorithm can find the lowest weighted path of s to t ⋅ for example, the shortest path). Dijkstra’s algorithm juga dapat mencari jalan terpendek dari satu puncak s ke sebarang puncak lain dalam satu carta ⋅ Di Dijkstra’s algorithm adalah sumber terpantas yang paling cepat diketahui untuk grafik berorientasikan tanpa beban.

Langkah algoritma:

• 1 , perintah awal S = {V0}, T = {tetinggi lain}, nilai jarak yang sesuai dengan puncak di T Jika terdapat , d ((V0,Vi) adalah nilai kuasa pada busur Jika tidak ada , d (V0, Vi) adalah∞

• 1. Pilih satu puncak dari T yang jaraknya adalah W dan tidak dalam S, dan masukkan ke dalam S

• 3 , Ubah nilai jarak ke puncak T yang lain: jika anda menambah W sebagai puncak tengah, kurangkan nilai jarak dari V0 ke Vi, ubah nilai jarak ini

  Ulangi langkah 2 dan 3 di atas sehingga S mengandungi semua puncak, iaitu W = Vi

• Algoritma 9: Algoritma perancangan dinamik

Pemrograman dinamik (Dynamicprogramming) adalah satu kaedah yang digunakan dalam matematik, sains komputer dan ekonomi untuk menyelesaikan masalah yang rumit dengan cara memecahkan masalah asal menjadi sub-masalah yang agak mudah. Pemrograman dinamik sering digunakan untuk masalah dengan masalah sub-masalah yang bertindih dan sifat struktur optimum, dan kaedah pemrograman dinamik sering memakan masa yang jauh lebih sedikit daripada penyelesaian yang sederhana.

Idea asas di sebalik perancangan dinamik sangat mudah. Secara amnya, jika kita ingin menyelesaikan masalah yang diberikan, kita perlu menyelesaikan bahagian-bahagian yang berlainan daripadanya (masalah anak), dan kemudian menggabungkan penyelesaian masalah anak untuk mendapatkan penyelesaian kepada masalah asal. Biasanya banyak masalah anak sangat serupa, untuk ini kaedah perancangan dinamik cuba menyelesaikan setiap masalah anak hanya sekali, dengan itu mengurangkan jumlah pengiraan: setelah penyelesaian kepada masalah anak yang diberikan telah dihitung, ia disimpan dalam ingatan, supaya ia dapat dipetik secara langsung pada masa berikutnya untuk menyelesaikan masalah anak yang sama.

Soalan klasik mengenai perancangan dinamik adalah mengenai beg galas.

Langkah algoritma:

1. Sifat struktur optimum. Jika penyelesaian subsoal yang terkandung dalam penyelesaian optimum masalah juga adalah yang terbaik, kita mengatakan bahawa masalah itu mempunyai sifat struktur optimum ((iaitu memenuhi prinsip optimum). Sifat struktur optimum memberikan petunjuk penting untuk menyelesaikan masalah dengan algoritma perancangan dinamik.

2 , sifat bertindih subsoal. Sifat bertindih subsoal adalah apabila menggunakan algoritma berulang dari atas ke bawah untuk menyelesaikan masalah, setiap subsoal yang dihasilkan tidak selalu menjadi masalah baru, beberapa subsoal akan dikira berulang kali. Algoritma perancangan dinamik memanfaatkan sifat bertindih subsoal ini, hanya dikira sekali untuk setiap subsoal, kemudian menyimpan hasil pengiraan dalam satu jadual, dan apabila perlu mengira subsoal yang telah dikira sekali lagi, hanya melihat hasilnya dalam jadual, sehingga mendapat kecekapan yang lebih tinggi.

• ### Algoritma 10: Algoritma Klasifikasi Bayesian Sederhana

Algoritma klasifikasi Bayesian sederhana adalah algoritma klasifikasi kebarangkalian sederhana berdasarkan teorema Bayesian. Algoritma klasifikasi Bayesian sederhana didasarkan pada penalaran kebarangkalian, iaitu bagaimana menyelesaikan tugas penalaran dan membuat keputusan jika terdapat pelbagai keadaan yang tidak pasti, hanya dengan mengetahui kebarangkalian mereka. Penalaran kebarangkalian adalah bersamaan dengan penalaran kepastian.

Klasifikator Bayesian sederhana bergantung kepada model kebarangkalian semula jadi yang tepat, yang menghasilkan hasil klasifikasi yang sangat baik dalam kepekatan sampel yang dipantau. Dalam banyak aplikasi praktikal, parameter model Bayesian sederhana dianggarkan menggunakan pendekatan anggaran kebarangkalian maksimum, iaitu model Bayesian sederhana berfungsi tanpa menggunakan kebarangkalian Bayesian atau model Bayesian apa pun.

Walaupun dengan pemikiran yang sederhana dan hipotesis yang terlalu mudah, klasifier Bayes yang sederhana masih boleh mencapai hasil yang cukup baik dalam banyak keadaan realiti yang kompleks.