Sortasi cepat adalah algoritma penyortiran yang dikembangkan oleh Tony Hall. Dalam kondisi rata-rata, penyortiran n item membutuhkan O (nlogn) perbandingan. Dalam kondisi terburuk, O (n2) perbandingan diperlukan, tetapi hal ini tidak umum. Bahkan, Sortasi cepat biasanya jauh lebih cepat daripada algoritma O (nlogn) lainnya karena loop dalamannya dapat diimplementasikan dengan sangat efisien di sebagian besar arsitektur.
Pengelompokan cepat menggunakan kebijakan pembagian dan penaklukan untuk membagi sebuah daftar menjadi dua sub-daftar.
Langkah algoritma:
1, memilih elemen dari baris bilangan, yang disebut pivot,
2, reorder baris, semua elemen yang lebih kecil dari nilai dasar ditempatkan di depan dasar, dan semua elemen yang lebih besar dari nilai dasar ditempatkan di belakang dasar (jumlah yang sama dapat pergi ke kedua sisi); setelah keluar dari partisi ini, dasar berada di tengah baris; ini disebut operasi partisi (partisi).
3, secara rekursif (recursive) mengurutkan subseries yang memiliki elemen yang lebih kecil dari nilai dasar dan subseries yang memiliki elemen yang lebih besar dari nilai dasar.
Dalam situasi paling dasar dari regresi, ukuran baris adalah nol atau satu, yang berarti selalu telah diurutkan dengan baik. Meskipun terus-menerus regresi, algoritma ini selalu keluar karena dalam setiap iterasi iterasi, ia menempatkan setidaknya satu elemen ke posisi terakhirnya.
Heapsort adalah sebuah algoritma penyortiran yang dirancang untuk menggunakan struktur data seperti heaps. Heapsort adalah struktur yang hampir sama dengan pohon biner, dan pada saat yang sama memenuhi sifat heapsort: yaitu nilai kunci atau indeks dari sub-node selalu lebih kecil dari (atau lebih besar dari) node induknya.
Kompleksitas rata-rata waktu pengurutan tumpukan adalah O (nlogn).
Langkah algoritma:
1, membuat H [0...n-1]
2, mengganti kepala tumpukan (max) dan ujung tumpukan
3, mengurangi ukuran heap menjadi 1 dan memanggil shift_down ((0), untuk menyesuaikan data di atas array baru ke posisi yang sesuai
4, ulangi langkah 2, sampai ukuran tumpukan adalah 1.
Mergesort adalah algoritma pengurutan yang efektif yang didasarkan pada operasi pengurutan. Algoritma ini adalah aplikasi yang sangat khas dari metode pembagian dan penaklukan.
Langkah algoritma:
1, aplikasi ruang, sehingga ukurannya menjadi jumlah dari dua urutan yang sudah disortir, ruang ini digunakan untuk menyimpan urutan yang telah digabungkan
2 ∞ Setel dua pointer dengan posisi awal masing-masing sebagai posisi awal dari dua urutan yang telah disortir
3, bandingkan elemen yang ditunjuk oleh dua pointer, pilih elemen yang relatif kecil, masukkan ke ruang gabungan, dan pindahkan pointer ke posisi berikutnya
4, ulangi langkah 3 sampai salah satu pointer mencapai ujung urutan
5, meng-copy semua elemen yang tersisa dari urutan lain langsung ke ujung urutan gabungan
Algoritma pencarian dengan dua titik adalah sebuah algoritma pencarian untuk mencari suatu elemen tertentu dalam suatu array tersusun. Proses pencarian dimulai dari elemen tengah array, dan jika elemen tengah adalah elemen yang akan dicari, proses pencarian berakhir; jika suatu elemen tertentu lebih besar atau lebih kecil dari elemen tengah, maka pencarian dilakukan di setengah dari array yang lebih besar atau lebih kecil dari elemen tengah, dan perbandingan dimulai dari elemen tengah seperti pada awal. Jika pada suatu langkah, himpunan kosong, maka tidak dapat ditemukan.
Masalah klasik yang harus diselesaikan oleh algoritma BFPRT, yaitu memilih elemen k besar (k kecil) dari rangkaian n elemen, dengan analisis yang cerdik, BFPRT dapat menjamin bahwa kompleksitas waktu masih linear pada situasi terburuk. Gagasan algoritma ini mirip dengan gagasan pengurutan cepat, tentu saja, untuk membuat algoritma tetap mencapai kompleksitas waktu o (n) pada situasi terburuk, lima penulis algoritma melakukan pengolahan yang halus.
Langkah algoritma:
1, dengan mengelompokkan n elemen ke dalam 5 kelompok, dibagi menjadi n/5 (atas batas) kelompok.
2. Mengambil median dari setiap kelompok, metode penyortiran arbitrer, seperti menyertakan penyortiran.
3, recursive call selection algorithm mencari median dari semua median pada langkah sebelumnya, yang ditetapkan sebagai x, dan dalam kasus median bilangan genap ditetapkan sebagai memilih yang terkecil di tengah.
4 {\displaystyle 4} untuk membagi suatu array dengan menggunakan x, dengan bilangan kurang dari x sama dengan k dan bilangan lebih besar dari x sama dengan n-k {\displaystyle n-k}
5, jika i==k, kembali x; jika i
Kondisi akhir: ketika n = 1, yang dikembalikan adalah elemen kecil i.
Deep-First-Search adalah sebuah algoritma pencarian. Algorithm ini menjelajahi titik-titik yang sangat dalam di sepanjang pohon, dengan cabang-cabang pohon yang terdalam mungkin. Ketika semua sisi titik v telah dieksplorasi, pencarian akan kembali ke titik awal di sisi titik v yang ditemukan. Proses ini berlangsung sampai semua titik yang telah ditemukan dapat diakses dari titik sumber. Jika tidak ada titik yang ditemukan, pilih salah satu dari titik-titik tersebut sebagai titik sumber dan ulangi proses ini, dan ulangi seluruh proses sampai semua titik diakses.
Pencarian terdepan adalah algoritma klasik dalam diagram. Dengan menggunakan algoritma pencarian terdepan, algoritma dapat menghasilkan topologi yang sesuai dengan grafik tujuan. Dengan menggunakan topologi, banyak masalah diagram terkait dapat diselesaikan dengan mudah, seperti masalah jalur terbesar, dan sebagainya.
Di bawah ini adalah langkah-langkah algoritma yang harus diutamakan:
1, akses ke puncak v;
2, mulai dari titik-titik tetangga v yang belum diakses, lalu melakukan penjelajahan prioritas kedalaman; sampai puncak-puncak di diagram yang memiliki jalur yang bersatu dengan v diakses;
3. Jika ada puncak yang belum diakses di grafik pada saat ini, mulai dari puncak yang belum diakses dan lakukan lagi penjelajahan prioritas kedalaman sampai semua puncak di grafik telah diakses.
Pernyataan di atas mungkin lebih abstrak, contohnya:
DFS memulai dari v, setelah memulai dengan puncak v di salah satu diagram akses, lalu pergi ke puncak w1 manapun yang berdekatan dengannya; kemudian pergi dari w1, lalu pergi ke puncak w2 yang berdekatan dengan puncak w1 tetapi belum pernah dikunjungi; kemudian pergi dari w2, lalu melakukan kunjungan serupa,... dan seterusnya, sampai mencapai puncak u di mana semua puncak berdekatan telah dikunjungi.
Kemudian, kembali ke puncak yang baru saja dikunjungi sebelumnya, untuk melihat apakah ada puncak tetangga lainnya yang belum dikunjungi. Jika ada, kunjungi puncak ini, dan kemudian mulai dari puncak ini untuk melakukan kunjungan serupa dengan yang sebelumnya; jika tidak, kembali ke langkah berikutnya untuk mencari. Ulangi proses di atas sampai semua puncak di diagram terhubung telah dikunjungi.
Breadth-First-Search adalah algoritma pencarian grafik. Secara sederhana, BFS adalah node yang berjalan di sepanjang lebar pohon, dimulai dari node akar. Jika semua node diakses, algoritma dihentikan.
Langkah algoritma:
Pertama, masukkan root node ke queue.
2, ambil node pertama dari queue dan periksa apakah itu adalah target.
Jika target ditemukan, search akan dihentikan dan hasil akan dikirim kembali. Jika tidak, semua subnode langsung yang belum diperiksa akan ditambahkan ke queue.
3. Jika baris kosong, berarti seluruh gambar telah diperiksa dan tidak ada target yang ingin dicari di gambar.
4 ∞ Ulangi langkah 2 ∞
Dijkstra's algorithm (Dijkstra's Salgorithm) adalah algoritme yang dikembangkan oleh ilmuwan komputer Belanda Eijzer Dijkstra. Dijkstra's algorithm menggunakan pencarian prioritas luas untuk memecahkan masalah jalur terpendek dari sumber tunggal dari grafik yang tidak negatif, yang akhirnya menghasilkan pohon jalur terpendek. Algoritma ini sering digunakan dalam algoritma routing atau sebagai sub-modul dari algoritma grafik lainnya.
Input dari algoritma ini terdiri dari sebuah gambar berorientasi G yang memiliki bobot, dan sebuah titik titik sumber S di G. Kita mewakili V sebagai himpunan semua titik puncak di G. Setiap sisi dalam gambar adalah pasangan elemen terorganisir yang dibentuk oleh dua titik puncak. U, v menunjukkan bahwa ada jalur yang terhubung dari titik puncak u ke v. Kita mewakili E sebagai himpunan semua sisi di G, sedangkan bobot sisi didefinisikan oleh fungsi bobot w: E → [0, ∞].
Oleh karena itu, w (u, v) adalah bobot non-negatif dari puncak u ke puncak v. Bobot sisi dapat dibayangkan sebagai jarak antara dua puncak. Bobot jalur antar dua titik adalah jumlah bobot semua sisi di jalur tersebut. Di V diketahui ada puncak s dan t, dan algoritma Dijkstra dapat menemukan jalur bobot minimum dari s ke t (misalnya, jalur terpendek). Algoritma ini juga dapat menemukan jalur terpendek dari puncak s ke puncak lain dalam sebuah grafik. Untuk grafik berorientasi yang tidak mengandung kekuatan negatif, algoritma Dijkstra adalah algoritma jalur terpendek tunggal tercepat yang diketahui saat ini.
Langkah algoritma:
1, nilai jarak yang sesuai dengan titik puncak di tengah T pada waktu awal S = {V0}, T = {sisa puncak}
Jika ada
2. Pilih dari T sebuah puncak W yang jaraknya paling kecil dan tidak ada di S, dan tambahkan S
3, mengubah nilai jarak dari puncak di T yang tersisa: mengubah nilai jarak ini dengan menambahkan W sebagai puncak tengah, mengurangi nilai jarak dari V0 ke Vi
Ulangi langkah 2 atau 3 di atas sampai semua titik di dalam S, yaitu W = Vi.
Pemrograman dinamis adalah metode yang digunakan dalam matematika, ilmu komputer, dan ekonomi untuk memecahkan masalah yang kompleks dengan cara memecah masalah awal menjadi sub-masalah yang relatif sederhana. Pemrograman dinamis sering digunakan untuk masalah yang memiliki sifat struktur sub-overlapping dan optimal, metode pemrograman dinamis seringkali membutuhkan waktu jauh lebih sedikit daripada solusi sederhana.
Gagasan dasar di balik perencanaan dinamis sangat sederhana. Secara umum, untuk memecahkan masalah tertentu, kita perlu memecahkan bagian-bagian yang berbeda (masalah anak), dan menyelesaikan masalah anak yang digabungkan kembali untuk menyelesaikan masalah asli. Seringkali banyak masalah anak yang sangat mirip, sehingga perencanaan dinamis mencoba untuk memecahkan setiap masalah anak hanya sekali, sehingga mengurangi jumlah perhitungan: setelah solusi untuk masalah anak tertentu telah dihitung, penyimpanan memorialnya disimpan, sehingga saat berikutnya yang dibutuhkan untuk memecahkan masalah anak yang sama langsung diperiksa. Praktik ini sangat berguna ketika jumlah masalah anak berulang meningkat secara indeks terhadap ukuran input.
Pertanyaan klasik tentang perencanaan dinamis adalah tentang tas ransel.
Langkah algoritma:
1, sifat struktural paling optimal. Jika solusi dari subproblem yang terkandung dalam solusi optimal dari suatu masalah juga optimal, maka kita mengatakan bahwa masalah tersebut memiliki sifat struktural paling optimal (yaitu memenuhi prinsip optimasi terbaik).
2, sifat overlapping subproblem... sifat overlapping subproblem adalah bahwa ketika menggunakan algoritma recursion untuk memecahkan masalah dari atas ke bawah, subproblem yang dihasilkan tidak selalu merupakan masalah baru setiap kali, dan beberapa subproblem akan dihitung berulang kali... algoritma perencanaan dinamis memanfaatkan sifat overlapping subproblem seperti ini, menghitung setiap subproblem hanya sekali, dan kemudian menyimpan hasil perhitungan mereka dalam sebuah tabel, dan ketika Anda perlu menghitung subproblem yang telah dihitung lagi, hanya melihat hasilnya secara sederhana dalam tabel untuk mendapatkan efisiensi yang lebih tinggi...
Algoritma klasifikasi Bayesian sederhana adalah algoritma klasifikasi probabilitas sederhana yang didasarkan pada teorema Bayesian. Algorithma klasifikasi Bayesian didasarkan pada penalaran probabilitas, yaitu bagaimana menyelesaikan tugas penalaran dan pengambilan keputusan dalam keadaan ketidakpastian berbagai kondisi, hanya dengan mengetahui kemungkinan mereka. Penalaran probabilitas sesuai dengan penalaran kepastian.
Classifier Bayesian sederhana mengandalkan model probabilitas alami yang akurat dan memiliki efek klasifikasi yang sangat baik pada kumpulan sampel dengan pembelajaran yang diawasi. Dalam banyak aplikasi praktis, estimasi parameter model Bayesian sederhana menggunakan estimasi yang paling mirip, yang berarti bahwa model Bayesian sederhana bekerja tanpa menggunakan probabilitas Bayesian atau model Bayesian apa pun.
Meskipun dengan ide-ide sederhana dan asumsi-asumsi yang terlalu sederhana, pemeringkat Bayesian sederhana dapat bekerja dengan cukup baik dalam banyak situasi realitas yang kompleks.