Pengatur Cepat adalah satu algoritma pengatur yang dibangunkan oleh Tony Hall. Dalam keadaan purata, pengatur n item memerlukan O (nlogn) perbandingan. Dalam keadaan terburuk, pengatur Cepat memerlukan O (n2) perbandingan, tetapi keadaan ini tidak biasa. Malah, pengatur Cepat biasanya lebih cepat daripada algoritma O (nlogn) yang lain, kerana gelung dalamannya dapat dilaksanakan dengan cekap di kebanyakan struktur.
Pengaturcaraan cepat menggunakan strategi pembahagian dan penaklukan untuk membahagikan satu senarai kepada dua senarai kecil.
Langkah algoritma:
1. Pilih satu elemen dari barisan nombor, yang dipanggil pivot.
2 ā Mengurut semula barisan nombor, semua elemen yang lebih kecil daripada nilai rujukan diletakkan di hadapan rujukan, dan semua elemen yang lebih besar daripada nilai rujukan diletakkan di belakang rujukan (jumlah yang sama boleh pergi ke mana-mana sisi); selepas pemisahan ini keluar, rujukan berada di tengah barisan; ini dipanggil operasi pemisahan (partition).
3, recursive: mengurutkan sub-unsur yang mempunyai unsur yang lebih kecil daripada nilai rujukan dan sub-unsur yang mempunyai unsur yang lebih besar daripada nilai rujukan.
Keadaan terendah untuk regresi ialah saiz barisan bilangan adalah sifar atau satu, yang bermaksud bahawa ia sentiasa telah diurutkan dengan baik. Walaupun terus regresi, algoritma ini akan selalu keluar, kerana dalam setiap iterasi, ia akan meletakkan sekurang-kurangnya satu elemen ke kedudukan terakhirnya.
Heapsort adalah algoritma penyortiran yang direka untuk menggunakan struktur data seperti heaps. Heapsort adalah struktur yang hampir sama dengan pokok binari dan juga memenuhi sifat heapsort: iaitu nilai kunci atau indeks titik anak sentiasa lebih kecil daripada titik induknya.
Kompleksiti masa purata penyusunan tumpukan adalah O (nlogn).
Langkah algoritma:
1. Buat H [0...n-1]
2, menukar kepala (maximum) dan ekor
3. Kurangkan saiz barisan dengan 1 dan panggil shift_down ((0), bertujuan untuk menyesuaikan data di puncak array baru ke kedudukan yang sesuai
4. Ulangi langkah 2, sehingga saiz timbunan adalah 1.
Mergesort adalah satu algoritma penyortiran yang berkesan yang dibina di atas operasi penggabungan. Algoritma ini adalah satu aplikasi yang sangat tipikal dengan menggunakan kaedah pembahagian dan menakluk.
Langkah algoritma:
1, aplikasi ruang, sehingga saiznya adalah jumlah dua siri yang telah diurutkan, ruang ini digunakan untuk menyimpan siri yang digabungkan
2. Tetapkan dua penunjuk dengan kedudukan awal masing-masing sebagai kedudukan permulaan dua siri yang telah diurutkan
3. Bandingkan elemen yang diarahkan oleh dua penunjuk, pilih elemen yang agak kecil dan masukkan ke ruang gabungan dan gerakkan penunjuk ke lokasi seterusnya
4. Ulangi langkah 3 sehingga satu penunjuk mencapai hujung siri.
5, menyalin semua elemen yang tinggal dalam siri lain secara langsung ke hujung siri gabungan
Algoritma carian dua titik adalah algoritma carian untuk mencari elemen tertentu dalam matriks tersusun. Proses carian bermula dari elemen tengah matriks, dan jika elemen tengah adalah elemen yang hendak dicari, proses carian berakhir; jika elemen tertentu lebih besar atau lebih kecil daripada elemen tengah, carian dilakukan di separuh daripada matriks yang lebih besar atau lebih kecil daripada elemen tengah, dan perbandingan bermula dari elemen tengah seperti pada mulanya. Jika pada satu langkah matriks kosong, maka tidak dapat dijumpai.
Masalah klasik yang diselesaikan oleh algoritma BFPRT, iaitu memilih elemen k terbesar (k kecil) dari siri n elemen, melalui analisis yang cerdik, BFPRT dapat menjamin bahawa kompleksiti masa yang masih linear dalam keadaan terburuk. Idea algoritma ini serupa dengan idea penyusunan cepat, tentu saja, untuk memastikan algoritma masih mencapai kompleksiti masa o (n) dalam keadaan terburuk, lima penulis algoritma melakukan pengolahan yang halus.
Langkah algoritma:
1, membahagikan n elemen kepada 5 kumpulan, dan membahagikan kepada kumpulan n/5 (di atas).
2. Mengambil nombor tengah dari setiap kumpulan, kaedah penyusunan yang tidak disukai, seperti menyisipkan penyusunan.
3. Algoritma pemilihan panggilan yang berulang mencari purata semua purata dalam langkah sebelumnya, ditetapkan sebagai x, dan dalam kes purata bilangan genap, ditetapkan sebagai memilih yang kecil di tengah.
4, untuk membahagikan artifak dengan x, letakkan bilangan kecil yang sama dengan x sebagai k, dan bilangan yang lebih besar daripada x adalah n - k.
5. Jika i==k, pulangkan x; jika i
Syarat penamatan: apabila n = 1, yang dikembalikan ialah unsur kecil i.
Algoritma carian keutamaan mendalam (dalam bahasa Inggeris: depth-first-search) adalah satu jenis algoritma carian. Ia melintasi pokok yang mendalam di sepanjang pokok, dengan cabang pokok carian yang mendalam. Apabila semua sisi titik v telah dieksplorasi, carian akan kembali ke titik permulaan di sebelah titik v yang ditemui. Proses ini berterusan sehingga semua titik yang telah ditemui yang boleh dicapai dari titik sumber. Jika tidak ada titik yang ditemui, pilih salah satu daripada mereka sebagai titik sumber dan ulangi proses di atas, keseluruhan proses berulang sehingga semua titik telah dikunjungi.
Pencarian keutamaan yang mendalam adalah algoritma klasik dalam grafik, yang menggunakan algoritma carian keutamaan yang mendalam untuk menghasilkan jadual pemusatan topologi yang sesuai dengan grafik sasaran. Dengan menggunakan jadual pemusatan topologi, banyak masalah grafik yang berkaitan dapat diselesaikan dengan mudah, seperti masalah laluan terbesar, dan sebagainya.
Di bawah ini adalah beberapa langkah algoritma yang perlu diambil terlebih dahulu:
1, akses ke puncak v;
2. Mulakan dari titik-titik berdekatan v yang belum diakses, lalu lalui grafik dengan keutamaan kedalaman; sehingga puncak-puncak di dalam grafik yang mempunyai laluan yang bersesuaian dengan v diakses;
3. Jika pada masa ini terdapat lagi puncak yang belum dikunjungi, mulakan dari puncak yang belum dikunjungi dan lakukan lagi pelayaran keutamaan kedalaman sehingga semua puncak di dalam grafik telah dikunjungi.
Perkataan di atas mungkin agak abstrak, contohnya:
DFS bermula dari v, setelah bermula pada puncak v di salah satu daripada grafik akses, untuk mengakses mana-mana puncak berdekatan dengan itu, w1; kemudian bermula dari w1, untuk mengakses puncak yang berdekatan dengan w1 tetapi belum dilawati, w2; kemudian bermula dari w2, untuk melakukan lawatan yang sama,... dan seterusnya sehingga mencapai puncak u di mana semua puncak berdekatan telah dilawati.
Kemudian, ambil langkah ke belakang dan kembali ke puncak yang baru dikunjungi sebelum ini untuk melihat sama ada terdapat puncak berdekatan lain yang tidak dikunjungi. Jika ada, pergi ke puncak ini dan kemudian mulakan dari puncak ini untuk melakukan lawatan yang sama seperti yang dinyatakan di atas; jika tidak, kembali ke langkah ke belakang dan cari. Ulangi proses di atas sehingga semua puncak di dalam grafik sambungan telah dikunjungi.
Breadth-First-Search adalah algoritma carian grafik. Secara ringkasnya, BFS adalah sebuah algoritma yang bermula dari titik akar dan melintasi titik sepanjang lebar pokok. Jika semua titik diakses, algoritma akan dihentikan.
Langkah algoritma:
1. Pertama, letakkan nod akar ke dalam larik.
2. ambil nod pertama dari barisan dan periksa apakah ia adalah sasaran.
Jika sasaran dijumpai, berhenti cari dan hantar semula hasil. Jika tidak, masukkan semua subnode langsung yang belum diperiksa ke dalam larutan.
3. Jika barisan kosong, ia menunjukkan bahawa semua gambar telah diperiksa dan tidak ada sasaran yang ingin dicari di dalam gambar.
4. Ulangi langkah 2.
Algoritma dijkstra (dalam bahasa Inggeris: Dijkstra's algorithm) ialah algoritma yang dicipta oleh saintis komputer Belanda, Eijzer Dijkstra. Algoritma dijkstra menggunakan carian keutamaan luas untuk menyelesaikan masalah laluan terpendek sumber tunggal untuk grafik arah yang tidak negatif, yang akhirnya menghasilkan pokok laluan terpendek. Algoritma ini sering digunakan sebagai algoritma laluan atau sebagai sub-modul kepada algoritma grafik lain.
Input kepada algoritma ini terdiri daripada satu gambar berwajaran G, dan satu puncak sumber S dalam G. Kita melambangkan V sebagai set semua puncak dalam G. Setiap sisi dalam grafik adalah pasangan unsur tertib yang diwujudkan oleh dua puncak. U, v menunjukkan terdapat laluan yang disambungkan dari puncak u ke v. Kita melambangkan E sebagai set semua sisi dalam G, dan berat sisi didefinisikan oleh fungsi bobot w:Eā[0,ā].
Oleh itu, w (u, v) adalah berat tidak negatif dari puncak u ke puncak v. Berat sisi boleh dibayangkan sebagai jarak antara dua puncak. Berat laluan antara dua titik adalah jumlah berat semua sisi di laluan itu. Terdapat puncak s dan t yang diketahui di V, dan algoritma Dijkstra dapat mencari laluan berat minimum dari s ke t. Contohnya, laluan terpendek.
Langkah algoritma:
1, nilai jarak yang sepadan dengan titik puncak di tengah T, apabila S = {V0}, T = {selebihnya titik puncak} pada waktu awal
Jika terdapat
2. Pilih satu puncak dari T yang jaraknya adalah minimum W dan tidak berada di dalam S, dan tambah S
3, mengubah nilai jarak kepada puncak di T yang selebihnya: mengubah nilai jarak ini apabila menambah W sebagai puncak tengah, mengurangkan nilai jarak dari V0 ke Vi
Ulangi langkah 2, 3 sehingga semua titik di dalam S, iaitu W = Vi
Pengaturcaraan dinamik (bahasa Inggeris: dynamic programming) adalah satu kaedah yang digunakan dalam matematik, sains komputer dan ekonomi untuk menyelesaikan masalah yang kompleks dengan cara memecahkan masalah asal kepada masalah kecil yang agak mudah. Pengaturcaraan dinamik sering digunakan untuk masalah yang mempunyai masalah yang bertindih dan sifat struktur yang paling optimum, dan kaedah pengaturcaraan dinamik sering mengambil masa yang jauh lebih sedikit daripada penyelesaian sederhana.
Idea asas di sebalik perancangan dinamik adalah sangat mudah. Secara amnya, untuk menyelesaikan masalah tertentu, kita perlu menyelesaikan bahagian-bahagian yang berlainan (masalah anak), dan menyelesaikan masalah anak yang disatukan semula untuk menyelesaikan masalah asal. Seringkali, banyak masalah anak sangat serupa, oleh itu, perancangan dinamik cuba menyelesaikan setiap masalah anak hanya sekali, sehingga mengurangkan jumlah pengiraan: setelah penyelesaian untuk masalah anak tertentu dikira, ia disimpan secara memori supaya dapat diperiksa secara langsung pada masa akan datang apabila masalah anak yang sama diperlukan untuk diselesaikan.
Masalah klasik mengenai perancangan dinamik adalah masalah beg.
Langkah algoritma:
1. sifat struktur paling optimum. Jika penyelesaian kepada masalah yang paling optimum juga merupakan yang terbaik, maka masalah itu dikatakan mempunyai sifat struktur paling optimum (iaitu memenuhi prinsip optimum); sifat struktur paling optimum memberikan petunjuk penting untuk penyelesaian masalah dalam algoritma perancangan dinamik.
2, sifat tumpang tindih masalah anak. sifat tumpang tindih masalah anak bermaksud bahawa apabila masalah diselesaikan dari atas ke bawah dengan algoritma berulang, setiap kali masalah anak yang dihasilkan tidak selalu menjadi masalah baru, dan beberapa masalah anak akan dikira berulang kali. Algoritma perancangan dinamik memanfaatkan sifat tumpang tindih masalah anak ini, mengira setiap masalah anak hanya sekali, kemudian menyimpan hasil penghitungannya dalam satu jadual, apabila perlu dikira semula masalah anak yang telah dikira, hanya melihat hasil dalam jadual dengan mudah, untuk mendapatkan kecekapan yang lebih tinggi.
Algoritma pembagian Bayesian sederhana adalah algoritma pembagian kebarangkalian sederhana berdasarkan teorema Bayesian. Algoritma pembagian Bayesian berasaskan penalaran kebarangkalian, iaitu bagaimana menyelesaikan tugas penalaran dan membuat keputusan di mana pelbagai keadaan tidak pasti, hanya dengan mengetahui kebarangkalian mereka. Penalaran kebarangkalian sejajar dengan penalaran kepastian.
Pengelasan Bayesian sederhana bergantung kepada model kebarangkalian semula jadi yang tepat dan dapat mencapai kesan klasifikasi yang sangat baik dalam kumpulan sampel dengan pembelajaran yang dipantau. Dalam banyak aplikasi praktikal, anggaran parameter Bayesian sederhana menggunakan kaedah anggaran kemiripan maksimum, dalam erti kata lain, model Bayesian sederhana berfungsi tanpa menggunakan kemungkinan Bayesian atau mana-mana model Bayesian.
Walaupun dengan idea-idea sederhana dan hipotesis yang terlalu mudah, pemeringkat Bayes yang sederhana dapat berfungsi dengan baik dalam banyak situasi realiti yang kompleks.