Sepuluh algoritma praktis dasar yang harus diketahui programmer dan penjelasannya

• ### Algoritma 1: Algoritma Sorting Cepat

Sorting cepat adalah sebuah algoritma pengurutan yang dikembangkan oleh Tony Hall. Dalam kondisi rata-rata, pengurutan n item membutuhkan O (nlogn) kali perbandingan. Dalam kondisi terburuk, diperlukan O (n2) kali perbandingan, tetapi ini tidak umum. Bahkan, sorting cepat biasanya lebih cepat dari algoritma O (nlogn) lainnya, karena lingkaran dalamnya (innerloop) dapat diimplementasikan dengan sangat efisien pada sebagian besar arsitektur.

Sorting cepat menggunakan strategi Divideandconquer untuk membagi sebuah daftar berurutan menjadi dua sub-daftar berurutan.

Langkah-langkah algoritma:

• 1. Pilih satu elemen dari array, yang disebut pivot.
• 1. Urut ulang array, semua elemen yang lebih kecil dari nilai acuan diletakkan di depan acuan, semua elemen yang lebih besar dari nilai acuan diletakkan di belakang acuan (dengan jumlah yang sama bisa ke salah satu sisi). Setelah keluar dari partisi ini, acuan berada di tengah-tengah array.
• 1. Recursively ((recursive) mengurutkan himpunan bagian yang lebih kecil dari elemen acuan dan himpunan bagian yang lebih besar dari elemen acuan.

  Dalam kasus paling mendasar dari iterasi, ukuran bilangan adalah nol atau satu, yang berarti bahwa semuanya telah disortir. Meskipun terus berurutan, algoritma ini akan selalu keluar, karena dalam setiap iterasi, ia akan menempatkan setidaknya satu elemen ke posisi terakhirnya.

• ### Algoritma 2: Algoritma Sorting Heap

Heapsort adalah sebuah algoritma pengurutan yang dirancang dengan menggunakan struktur data heapsort. Heapsort adalah sebuah struktur yang mirip dengan pohon biner yang sempurna, dan pada saat yang sama memenuhi sifat dari heapsort: yaitu nilai kunci atau indeks dari subnode selalu lebih kecil dari (atau lebih besar dari) node induknya.

Kompleksitas waktu rata-rata dari urutan tumpukan adalah O ((nlogn) 。

Langkah-langkah algoritma:

• 1. Membuat H-stack[0..n-1]
• 1. Ganti header (maksimal) dengan backend
• 1. Kurangi ukuran heap menjadi 1, dan panggil shift_down ((0)), untuk menyesuaikan data di puncak array baru ke posisi yang sesuai
• 1. Ulangi langkah 2 sampai tumpukan berukuran 1

• Algoritma 3: Penggabungan Urutan

Mergesort adalah sebuah algoritma pengurutan yang efektif berdasarkan operasi penggabungan. Algoritma ini adalah aplikasi yang sangat khas dari DivideandConquer.

Langkah-langkah algoritma:

• 1. Menggunakan ruang yang berukuran jumlah dari dua urutan yang telah diurutkan untuk menyimpan urutan yang telah digabungkan

• 2 , Setting dua pointer, posisi awal masing-masing sebagai dua posisi awal dari urutan yang telah diurutkan

• 1. Bandingkan dua elemen yang ditunjuk oleh penunjuk, pilih elemen yang relatif kecil untuk dimasukkan ke ruang gabungan, dan gerakkan penunjuk ke posisi berikutnya
• 1. Ulangi langkah 3 sampai salah satu penunjuk mencapai akhir urutan
• 1. Menyalin semua elemen yang tersisa dari urutan lain langsung ke akhir urutan gabungan

• Algoritma 4: Algoritma pencarian dua bagian

Algoritma pencarian biner adalah algoritma pencarian untuk menemukan elemen tertentu dalam array terurutan. Proses pencarian dimulai dari elemen tengah array, dan jika elemen tengah adalah elemen yang dicari, proses pencarian berakhir; jika elemen tertentu lebih besar atau lebih kecil dari elemen tengah, maka pencarian dimulai pada setengah dari array yang lebih besar atau lebih kecil dari elemen tengah, dan perbandingan dimulai dari elemen tengah seperti yang dimulai. Jika pada langkah tertentu jumlahnya kosong, maka tidak dapat ditemukan.

• ### Algoritma 5: BFPRT (algorithm pencarian linier)

Masalah yang diselesaikan oleh algoritma BFPRT sangat klasik, yaitu memilih elemen ke-k besar (atau ke-k kecil) dari urutan n elemen, dengan analisis yang cerdik, BFPRT dapat menjamin kompleksitas waktu linier dalam kasus terburuk. Gagasan algoritma ini mirip dengan pemikiran urutan cepat, tentu saja, untuk membuat algoritma dalam kasus terburuk, masih dapat mencapai kompleksitas waktu o (n), lima penulis algoritma melakukan pengolahan yang halus.

Langkah-langkah algoritma:

• 1. Tentukan n elemen dari setiap 5 kelompok, dibagi menjadi n/5 (batas atas) kelompok.
• 1. Keluarkan digit tengah dari setiap kelompok, dan pilih metode pengurutan, seperti menyisipkan pengurutan.
• 1. Algoritma recursive call selection mencari median dari semua median dalam langkah sebelumnya, dengan set x, dan dengan beberapa median yang genap, pilih yang kecil di tengah.
• 1. Pembagian array dengan x, dengan bilangan yang lebih kecil dari dan sama dengan x adalah k, dan bilangan yang lebih besar dari x adalah n-k.

• 5 , jika i == k, kembali x; jika i < k, berulangkali mencari elemen terkecil i dalam elemen yang lebih kecil dari x; jika i> k, berulangkali mencari elemen terkecil i-k dalam elemen yang lebih besar dari x.

  Kondisi akhir: jika n = 1, yang dikembalikan adalah elemen kecil i.

• Algoritma 6: DFS (Deep Priority Search)

Deep-First-Search, adalah sebuah algoritma pencarian yang berjalan sepanjang kedalaman sebuah pohon, dan mencari cabang-cabang pohon yang setinggi mungkin. Ketika semua sisi dari node v telah dijelajahi, pencarian akan kembali ke titik awal dari sisi yang menemukan node v. Proses ini terus dilakukan sampai semua node yang dapat dicapai dari node sumber yang telah ditemukan selesai. Jika masih ada node yang belum ditemukan, pilih salah satu dari mereka sebagai node sumber dan ulangi proses di atas, seluruh proses berulang sampai semua node telah diakses selesai.

Pencarian prioritas kedalaman adalah algoritma klasik dalam teori grafik, menggunakan algoritma pencarian prioritas kedalaman dapat menghasilkan tabel topologi yang sesuai dengan peta target, menggunakan tabel topologi dapat dengan mudah memecahkan banyak masalah grafik yang terkait, seperti masalah jalur maksimum, dll. Umumnya menggunakan struktur data tumpukan untuk membantu menerapkan algoritma DFS.

Langkah-langkah algoritma dengan prioritas mendalam:

• 1 , Kunjungi puncak v;

• 2 . Berangkat dari titik-titik tetangga yang tidak dikunjungi dari v berurutan, melakukan perjalanan ke dalam dengan prioritas; sampai titik-titik puncak yang memiliki jalur yang sama dengan v di dalam grafik dikunjungi;

• 1. Jika ada puncak yang belum dikunjungi pada peta waktu ini, mulailah dari puncak yang belum dikunjungi, dan ulangi perjalanan prioritas kedalaman sampai semua puncak di peta telah dikunjungi.

  Deskripsi di atas mungkin lebih abstrak, sebagai contoh:

  Setelah DFS memulai suatu titik puncak v dalam peta akses, ia akan berangkat dari v dan mengunjungi titik puncak tetangga yang berdekatan dengan titik puncak w1; kemudian ia akan berangkat dari w1 dan mengunjungi titik puncak yang berdekatan dengan titik puncak w1 tetapi belum pernah dikunjungi; kemudian ia akan berangkat dari w2 dan melakukan kunjungan yang serupa, … dan seterusnya, sampai ia mencapai titik puncak u yang telah dikunjungi oleh semua titik puncak tetangga tersebut.

  Selanjutnya, mundur selangkah, kembali ke puncak yang baru saja dikunjungi pada kunjungan sebelumnya, dan lihat apakah ada puncak berdekatan lainnya yang belum dikunjungi. Jika ada, kunjungi puncak ini, dan kemudian mulai dari puncak ini, lakukan kunjungan yang serupa dengan yang sebelumnya; jika tidak, kembali selangkah lagi untuk melakukan pencarian. Ulangi proses di atas sampai semua puncak dalam peta koneksi telah dikunjungi.

• Algoritma 7: BFS (Broad Foresight Prioritized Search)

Breadth-First-Search (BFS) adalah sebuah algoritma pencarian grafik. Secara sederhana, BFS adalah sebuah algoritma pencarian yang dimulai dari node root dan berjalan di sepanjang lebar pohon. Jika semua node diakses, algoritma akan berhenti.

Langkah-langkah algoritma:

• Pertama, masukkan node root ke dalam antrian.

• 1. Keluarkan node pertama dari antrian dan periksa apakah itu adalah target.

  Jika target ditemukan, hentikan pencarian dan kirimkan hasilnya. Jika tidak, masukkan semua sub node langsung yang belum diperiksa ke dalam antrian.

• 3 , Jika baris kosong, berarti seluruh peta telah diperiksa. Artinya tidak ada target yang ingin dicari dalam peta. Mengakhiri pencarian dan kembali ke pengirim tidak dapat menemukan target .

• 1. Ulangi langkah 2.

• Algoritma 8: Algoritma Dijkstra

Algoritma Dikstra (bahasa Belanda: Dijkstra-salgoritme) adalah sebuah algoritma yang dikembangkan oleh seorang ilmuwan komputer asal Belanda bernama Eizhel Dijkstra. Algoritma Dikstra menggunakan pencarian prioritas luas untuk memecahkan masalah sumber tunggal yang paling pendek dari sebuah grafik berorientasi nonnegatif. Algoritma ini sering digunakan dalam algoritma routing atau sebagai sub-modul dari algoritma grafik lainnya.

Input dari algoritma ini berisi sebuah oriented graph G dengan berat, dan sebuah sumber vertebrata S di dalam G. Kita mewakili dengan V himpunan semua vertebrata di dalam G. Di dalam setiap grafik, sisi adalah dua elemen berurutan yang dibentuk oleh dua vertebrata. Di dalam u, v terdapat jalur yang terhubung dari vertebrata u ke v. Kita mewakili dengan E himpunan semua sisi di dalam G, dan berat sisi ditentukan oleh fungsi berat w:E→[0,∞] didefinisikan.

Oleh karena itu, w (u,v) adalah berat non-negatif dari titik u ke titik v. Berat sisi dapat dibayangkan sebagai jarak antara dua titik. Berat dari jalur antara dua titik adalah jumlah berat dari semua sisi pada jalur tersebut.

Langkah-langkah algoritma:

• 1, waktu awal S = {V0}, T = {tetap titik}, nilai jarak dari titik titik T Jika ada , d ((V0,Vi) adalah nilai berat pada Jika tidak ada , d (V0, Vi) adalah ∞

• 1. Pilih dari T sebuah puncak yang jaraknya paling kecil W dan tidak ada dalam S, dan tambahkan S

• 3 , mengubah nilai jarak dari puncak di T lainnya: jika menambahkan W sebagai puncak tengah, jarak dari V0 ke Vi dikurangi, maka nilai jarak ini diubah

  Ulangi langkah 2 dan 3 di atas sampai S mencakup semua puncak, yaitu W = Vi

• Algoritma 9: Algoritma Perencanaan Dinamis

Pemrograman dinamis (bahasa Inggris: dynamic programming) adalah sebuah metode yang digunakan dalam matematika, ilmu komputer, dan ekonomi untuk memecahkan masalah kompleks dengan cara memecah masalah asli menjadi sub-masalah yang relatif sederhana. Pemrograman dinamis sering digunakan untuk masalah dengan sub-masalah yang tumpang tindih dan struktur optimal, dan metode pemrograman dinamis seringkali memakan waktu jauh lebih sedikit daripada solusi sederhana.

Ide dasar di balik perencanaan dinamis sangat sederhana. Secara umum, jika kita ingin memecahkan masalah tertentu, kita perlu memecahkan bagian-bagian yang berbeda dari masalah tersebut, kemudian menggabungkan solusi dari masalah anak untuk mendapatkan solusi dari masalah asal. Biasanya banyak masalah anak yang sangat mirip, untuk ini perencanaan dinamis mencoba untuk hanya menyelesaikan setiap masalah anak sekali, sehingga mengurangi jumlah perhitungan: setelah solusi dari masalah anak tertentu telah dihitung, itu disimpan dalam memori, sehingga pada waktu berikutnya diperlukan untuk memecahkan masalah anak yang sama.

Pertanyaan yang paling klasik tentang perencanaan dinamis adalah pertanyaan tentang ransel.

Langkah-langkah algoritma:

1. Struktur optimal. Jika solusi optimal untuk sub-masalah yang terkandung dalam solusi optimal untuk masalah tersebut juga merupakan solusi optimal, maka kita mengatakan bahwa masalah tersebut memiliki struktur optimal (yang memenuhi prinsip optimasi). Struktur optimal memberikan petunjuk penting untuk memecahkan masalah dengan algoritma perencanaan dinamis.

2 , masalah anak yang tumpang tindih sifat . Masalah anak yang tumpang tindih sifat adalah bahwa setiap kali masalah anak yang dihasilkan tidak selalu masalah baru, beberapa masalah anak akan dihitung berulang kali . Algoritma perencanaan dinamis memanfaatkan masalah anak yang tumpang tindih sifat ini, untuk setiap masalah anak hanya dihitung sekali, dan kemudian menyimpan hasil perhitungan di dalam sebuah tabel, ketika perlu untuk menghitung masalah anak yang telah dihitung lagi, hanya melihat hasil di dalam tabel, sehingga mendapatkan efisiensi yang lebih tinggi .

• ### Algoritma 10: Algoritma klasifikasi Bayesian sederhana

Klasifikasi Bayesian sederhana adalah algoritma klasifikasi probabilitas sederhana yang didasarkan pada teorema Bayesian. Klasifikasi Bayesian didasarkan pada penalaran probabilitas, yaitu bagaimana menyelesaikan tugas penalaran dan pengambilan keputusan dalam berbagai kondisi yang tidak pasti, hanya dengan mengetahui probabilitasnya. Penalaran probabilitas adalah korespondensi dari penalaran determinisme.

Klasifikator Bayesian sederhana bergantung pada model probabilitas alami yang akurat, dan dapat memperoleh hasil klasifikasi yang sangat baik pada konsentrasi sampel dengan pembelajaran yang diawasi. Dalam banyak aplikasi praktis, parameter model Bayesian sederhana diperkirakan menggunakan metode perkiraan ke-kiraan terbesar, yang berarti bahwa model Bayesian sederhana dapat bekerja tanpa menggunakan probabilitas Bayesian atau model Bayesian apa pun.

Meskipun dengan pemikiran yang sederhana dan asumsi yang terlalu sederhana, klasifikasi Bayesian sederhana masih dapat mencapai hasil yang cukup baik dalam banyak situasi realitas yang kompleks.