Jenis Algoritma
Algoritma Sorting
Algoritma Sorting merupakan algoritma yang menempatkan elemen list pada urutan tertentu.
Urutan yang paling sering digunakan ialah urutan numerikal dan urutan lexicographical.
Sorting yang efisien sangat dibutuhkan untuk mengoptimisasi penggunaan dari algoritma lain seperti pencarian dan penggabungan yang membutuhkan list terurut untuk berjalan dengan sempurna, yang juga sering digunakan untuk Canonicalisisasi data dan menghasilkan output yang dapat dibaca manusia. (Wikipedia)
Jenis Algoritma Sorting dan Implemetasinya dalam bahasa PHP*
PHP adalah singkatan rekursif untuk "PHP: Hypertext Preprocessor", yaitu bahasa pemrograman yang digunakan secara luas untuk penanganan pembuatan dan pengembangan sebuah situs web dan bisa digunakan bersamaan dengan HTML.
1. Buble Sort
Merupakan algoritma pengurutan paling tua dengan metode pengurutan paling sederhana. Pengurutan yang dilakukan dengan membandingkan masing-masing item dalam suatu list secara berpasangan, menukar item jika diperlukan, dan mengulaginya sampai akhir list secara berurutan, sehingga tidak ada lagi item yang dapat ditukar.
Implementasi :
echo "//bubble sortn";
$data=array(6,5,3,1,8,7,2,4);
function bubble_sort($data){
$n=count($data);
for ($i = 0;$i<$n;$i++){ for ($j = $n-1;$j>$i;$j--){
if ($data[$j] < $data[$j-1]){
$dummy=$data[$j];
$data[$j]=$data[$j-1];
$data[$j-1]=$dummy;
}
}
}
return $data;
}
print_r(bubble_sort($data));
2. Insertion Sort
Algoritma insertion sort pada dasarnya memilah data yang akan diurutkan menjadi dua bagian, yang belum diurutkan dan yang sudah diurutkan. Elemen pertama diambil dari bagian array yang belum diurutkan dan kemudian diletakkan sesuai posisinya pada bagian lain dari array yang telah diurutkan. Langkah ini dilakukan secara berulang hingga tidak ada lagi elemen yang tersisa pada bagian array yang belum diurutkan.
Implementasi :
echo "//insertion sortn";
$data=array(6,5,3,1,8,7,2,4);
function insertion_sort($data){
$n=count($data);
for ($i = 1;$i<$n;$i++){ for ($k = $i; $k>0; $k--) {
if($data[$k]<$data[$k-1]){
$dummy=$data[$k];
$data[$k]=$data[$k-1];
$data[$k-1]=$dummy;
}
}
}
return $data;
}
print_r(insertion_sort($data));
3. Selection Sort
Ide utama dari algoritma selection sort adalah memilih elemen dengan nilai paling rendah dan menukar elemen yang terpilih dengan elemen ke-i. Nilai dari i dimulai dari 1 ke n, dimana n adalah jumlah total elemen dikurangi 1.
Implementasi
echo "//selection sortn";
$data=array(6,5,3,1,8,7,2,4);
function selection_sort($data){
$n=count($data);
for ($i = 0;$i<$n;$i++){
$k = $i;
for ($j = $i+1;$j<$n;$j++){
if ($data[$j] < $data[$k]) $k = $j;
}
$dummy=$data[$i];
$data[$i]=$data[$k];
$data[$k]=$dummy;
}
return $data;
}
print_r(selection_sort($data));
4. Shell Sort
Merupakan algoritma yang stau jenis dengan insertion sort, dimana pada setiap nilai i dalam n/i item diurutkan. Pada setiap pergantian nilai, i dikurangi sampai 1 sebagai nilai terakhir.
Implementasi :
echo "//shell sortn";
$data=array(6,5,3,1,8,7,2,4);
function shell_sort($data){
$n=count($data);
$k=0;
$gap[0]=(int) ($n / 2);
while($gap[$k]>1){
$k++;
$gap[$k]=(int)($gap[$k-1]/2);
}
for($i=0;$i<=$k;$i++){
$step=$gap[$i];
for($j=$step;$j<$n;$j++){
$temp=$data[$j];
$p=$j-$step;
while($p>=0 && $temp<$data[$p]){
$data[$p+$step]=$data[$p];
$p=$p-$step;
}
$data[$p+$step]=$temp;
}
}
return $data;
}
print_r(shell_sort($data));
5. Merge Sort
Algoritma dirumuskan dalam 3 langkah berpola divide-and-conquer. Berikut menjelaskan langkah kerja dari Merge sort.
- Divide : Memilah elemen – elemen dari rangkaian data menjadi dua bagian.
- Conquer : Conquer setiap bagian dengan memanggil prosedur merge sort secara rekursif
- Kombinasi : Mengkombinasikan dua bagian tersebut secara rekursif untuk mendapatkan rangkaian data berurutan
Proses rekursi berhenti jika mencapai elemen dasar. Hal ini terjadi bilamana bagian yang akan diurutkan menyisakan tepat satu elemen. Sisa pengurutan satu elemen tersebut menandakan bahwa bagian tersebut telah terurut sesuai rangkaian.
Implementasi :
echo "//merge sortn";
$data=array(6,5,3,1,8,7,2,4);
function merge_sort ($data){
if (count($data) <= 1 ) return $data;
$left = merge_sort(array_splice($data,floor(count($data) / 2)));
$right = merge_sort($data);
$result = array();
while (count($left) > 0 && count($right) > 0){
if ($left[0] <= $right[0])
array_push($result, array_shift($left));
else
array_push($result, array_shift($right));
}
while (count($left) > 0)
array_push($result, array_shift($left));
while (count($right) > 0)
array_push($result, array_shift($right));
return $result;
}
print_r(merge_sort($data));
6. Quick Sort
Algoritma ini berdasar pada pola divide-and-conquer. Berbeda dengan merge sort, algoritma ini hanya mengikuti langkah – langkah sebagai berikut :
- Divide
Memilah rangkaian data menjadi dua sub-rangkaian A[p…q-1] dan A[q+1…r] dimana setiap elemen A[p…q-1] adalah kurang dari atau sama dengan A[q] dan setiap elemen pada A[q+1…r] adalah lebih besar atau sama dengan elemen pada A[q]. A[q] disebut sebagai elemen pivot. Perhitungan pada elemen q merupakan salah satu bagian dari prosedur pemisahan.
- Conquer
Mengurutkan elemen pada sub-rangkaian secara rekursif. Pada algoritma quicksort, langkah ”kombinasi” tidak di lakukan karena telah terjadi pengurutan elemen – elemen pada sub-array.
Implementasi :
echo "//quick sortn";
$data=array(6,5,3,1,8,7,2,4);
function quick_sort($data) {
if(!count($data)) return $data;
$pivot= $data[0];
$low = $high = array();
$n = count($data);
for($i=1; $i < $n; $i++) {
if($data[$i] <= $pivot) {
$low [] = $data[$i];
} else {
$high[] = $data[$i];
}
}
return array_merge(quick_sort($low), array($pivot), quick_sort($high));
}
print_r(quick_sort($data));
7. Heap Sort
Heap sort adalah sorting yang menggunakan struktur data heap, dengan nilai parent selalu lebih besar dari pada nilai childnya.
Algoritma :
- Buat suatu heap.
- Ambil isi dari root masukkan kedalam sebuah array.
- Hapus element root dengan mempertahankan properti heap.
- Ulangi sampai tree menjadi kosong
Implementasi :
echo "//heap sortn";
$data=array(6,5,3,1,8,7,2,4);
function build_heap(&$data, $i, $t){
$tmp_var = $data[$i];
$j = $i * 2 + 1;
while ($j <= $t) {
if($j < $t)
if($data[$j] < $data[$j + 1]) {
$j = $j + 1;
}
if($tmp_var < $data[$j]) {
$data[$i] = $data[$j];
$i = $j;
$j = 2 * $i + 1;
} else {
$j = $t + 1;
}
}
$data[$i] = $tmp_var;
}
function heap_sort(&$data) {
$init = (int)floor((count($data) - 1) / 2);
for($i=$init; $i >= 0; $i--){
$count = count($data) - 1;
build_heap($data, $i, $count);
}
for ($i = (count($data) - 1); $i >= 1; $i--) {
$tmp_var = $data[0];
$data[0] = $data[$i];
$data[$i] = $tmp_var;
build_heap($data, 0, $i - 1);
}
}
heap_sort($data);
print_r($data);
Latihan
Coba terapkan kode pemroraman diatas pada > online php compiler ini
Algoritma Brute Force > Exhaustive Search
Sumber : DosenIT.com >
Banyak yang mengatakan bahwa algoritma brute force merupakan jenis algoritma yang sifatnya straight, lurus.
Algoritma brute force merupakan bentuk algoritma yang sangat kompleks, karena untuk dapat menyelesaikan masalah dengan teknik straight forward, untuk itu dibutuhkan banyak masukan dan juga pertimbangan secara logis, sehingga dapat diperoleh sebuah keputusan pemecahan masalah yag langsung mengacu atau menuju kepada hasil yang diinginkan.
Baca Juga : Bahasa Pemrograman Web Paling Populer , Jenis Firewall
Algoritma brute force ini biasanya menggunakan pendekatan yang disarkan pada pernyataan masalah atau problem statement, dan juga definisi konsep yang dilibatkan.
Dalam implementasinya, algoritma brute force ini membutuhkan sebuah cara yang jelas namun sederhana.
Kelebihan algoritma brute force
algoritma yang memecahkan masalah secara jelas, dan melalui banyak opini atau pilihan, maka
algoritma brute force merupakan sebuah metode pemecahan masalah logis yang memiliki kemampuan untuk memperoleh pemecahan masalah dengan baik.
mampu untuk menyaring satu dari sekian banyak solusi atau opsi yang ditawarkan,sehingga proses pemecahan masalah yang dilakukan akan menjadi lebih baik dan juga lebih optimal.
Hampir semua masalah yang dipecahkan dengan menggunakan metode algoritma brute force ini berjalan dengan baik.
Kelemahan dari algoritma brute force
algoritma brute force sangat sulit untuk digunakan pada kebutuhan pemecahan masalah yagn cepat.
algoritma brute force membutuhkan kumpulan banyak opsi terlebih dahulu sebulu dieksekusi.
pertimbangan dalam memilih opsi akan menjadi lebih lambat.
Exhaustive Search[sumber]
Terminologi lain yang terkait erat dengan brute force adalah exhaustive search.
Baik brute force maupun exhaustive search sering dianggap dua istilah yang sama, padahal dari jenis masalah yang dipecahkan ada sedikit perbedaan.
Exhaustive search adalah teknik pencarian solusi secara brute force pada masalah yang melibatkan pencarian elemen dengan sifat khusus, biasanya di antara objek-objek kombinatorik seperti permutasi, kombinasi, atau himpunan bagian dari sebuah himpunan. Berdasarkan definisi ini, maka exhaustive search adalah brute force juga.
Metode exhaustive search dapat dirumuskan langkah-langkahnya sebagai berikut:
1. Enumerasi (list) setiap solusi yang mungkin dengan cara yang sistematis.
2. Evaluasi setiap kemungkinan solusi satu per satu, mungkin saja beberapa kemungkinan solusi yang tidak layak dikeluarkan, dan simpan solusi terbaik yang ditemukan sampai sejauh ini (the best solusi found so far).
3. Bila pencarian berakhir, umumkan solusi terbaik (the winner)
Meskipun algoritma exhaustive secara teoritis menghasilkan solusi, namun waktu atau sumberdaya yang dibutuhkan dalam pencarian solusinya sangat besar.
Di dalam beberapa literatur strategi algoritmik, contoh masalah yang sering diasosiasikan dengan exhaustive search atau brute force adalah :
Masalah Travelling Salesperson Problem (TSP).
Exhaustive search juga sering disebut-sebut di dalam bidang kriptografi, yaitu sebagai teknik yang digunakan penyerang untuk menemukan knci enkripsi dengan cara mencoba semua kemungkinan kunci. Serangan semacam ini dikenal dengan nama exhaustive ke search attack atau brute force attack.
Misalnya pada algoritma kriptografi DES (Data Encryption Standard), panjang kunci enkripsi adalah 64 bit (atau setara dengan 8 karakter). Dari 64 bit tersebut, hanya 56 bit yang digunakan (8 bit paritas lainnya tidak dipakai). Karena ada 56 posisi pengisian bit yang masing-masing memiliki dua kemungkinan nilai, 0 atau 1, maka jumlah kombinasi kunci yang harus dievaluasi oleh pihak lawan adalah sebanyak
Meskipun algoritma exhaustive search tidak efektif, namun nilai plusnya terletak pada keberhasilannya yang selalu menemukan solusi (jika diberikan waktu yang cukup).
Algoritma Greedy
Sumber : dev.bertzzie.com >
Algoritma greedy merupakan jenis algoritma yang menggunakan pendekatan penyelesaian masalah dengan mencari nilai maksimum sementara pada setiap langkahnya.
Nilai maksimum sementara ini dikenal dengan istilah local maximum.
Pada kebanyakan kasus, algoritma greedy tidak akan menghasilkan solusi paling optimal, begitupun algoritma greedy biasanya memberikan solusi yang mendekati nilai optimum dalam waktu yang cukup cepat.
Sebagai contoh dari penyelesaian masalah dengan algoritma greedy, mari kita lihat sebuah masalah klasik yang sering dijumpai dalam kehidupan sehari-hari: mencari jarak terpendek dari peta. Misalkan kita ingin bergerak dari titik A ke titik B, dan kita telah menemukan beberapa jalur dari peta:
Dari peta yang ditampilkan di atas, dapat dilihat bahwa terdapat beberapa jalur dari titik A ke titik B. Sistem peta pada gambar secara otomatis telah memilih jalur terpendek (berwarna biru). Kita akan mencoba mencari jalur terpendek juga, dengan menggunakan algoritma greedy.
Langkah Algoritma Greedy
Langkah pertama yang harus kita lakukan tentunya adalah memilih struktur data yang tepat untuk digunakan dalam merepresentasikan peta. Jika dilihat kembali, sebuah peta seperti pada gambar di atas pada dasarnya hanya menunjukkan titik-titik yang saling berhubungan, dengan jarak tertentu pada masing-masing titik tersebut. Misalnya, peta di atas dapat direpresentasikan dengan titik-titik penghubung seperti berikut:
Dari gambar di atas, kita dapat melihat bagaimana sebuah peta jalur perjalanan dapat direpresentasikan dengan menggunakan graph, spesifiknya Directed Graph (graph berarah). Maka dari itu, untuk menyelesaikan permasalahan jarak terpendek ini kita akan menggunakan struktur data graph untuk merepresentasikan peta. Berikut adalah graph yang akan digunakan:
Graph Berarah dari Titik A ke B
Untuk mencari jarak terpendek dari A ke B, sebuah algoritma greedy akan menjalankan langkah-langkah seperti berikut:
- Kunjungi satu titik pada graph, dan ambil seluruh titik yang dapat dikunjungi dari titik sekarang.
- Cari local maximum ke titik selanjutnya.
- Tandai graph sekarang sebagai graph yang telah dikunjungi, dan pindah ke local maximum yang telah ditentukan.
- Kembali ke langkah 1 sampai titik tujuan didapatkan.
Jika mengapliikasikan langkah-langkah di atas pada graph A ke B sebelumnya maka kita akan mendapatkan pergerakan seperti berikut:
-
Mulai dari titik awal (A). Ambil seluruh titik yang dapat dikunjungi.
Langkah Pertama Greedy
-
Local maximum adalah ke C, karena jarak ke C adalah yang paling dekat.
-
Tandai A sebagai titik yang telah dikunjungi, dan pindah ke C.
-
Ambil seluruh titik yang dapat dikunjungi dari C.
Langkah Kedua Greedy
-
Local maximum adaah ke D, dengan jarak 6.
-
Tandai C sebagai titik yang telah dikunjungi, dan pindah ke D.
Langkah Ketiga Greedy
-
(Langkah selanjutnya diserahkan kepada pembaca sebagai latihan).
Dengan menggunakan algoritma greedy pada graph di atas, hasil akhir yang akan didapatkan sebagai jarak terpendek adalah A-C-D-E-F-B. Hasi jarak terpendek yang didapatkan ini tidak tepat dengan jarak terpendek yang sebenarnya (A-G-E-F-B). Algoritma greedy memang tidak selamanya memberikan solusi yang optimal, dikarenakan pencarian local maximum pada setiap langkahnya, tanpa memperhatikan solusi secara keseluruhan. Gambar berikut memperlihatkan bagaimana algoritma greedy dapat memberikan solusi yang kurang optimal:
Solusi Kurang Optimal dari Greedy
Tetapi ingat bahwa untuk kasus umum, kerap kali algoritma greedy memberikan hasil yang cukup baik dengan kompleksitas waktu yang cepat. Hal ini mengakibatkan algoritma greedy sering digunakan untuk menyelesaikan permasalahan kompleks yang memerlukan kecepatan jawaban, bukan solusi optimal, misalnya pada game.
Kesimpulan
Algoritma greedy merupakan algoritma yang besifat heuristik, mencari nilai maksimal sementara dengan harapan akan mendapatkan solusi yang cukup baik.
Meskipun tidak selalu mendapatkan solusi terbaik (optimum), algoritma greedy umumnya memiliki kompleksitas waktu yang cukup baik, sehingga algoritma ini sering digunakan untuk kasus yang memerlukan solusi cepat meskipun tidak optimal seperti sistem real-time atau game.
Dari impementasi yang kita lakukan, dapat dilihat bagaimana algoritma greedy memiliki beberapa fungsionalitas dasar, yaitu:
- Fungsi untuk melakukan penelusuran masalah.
- Fungsi untuk memilih local maximum dari pilihan-pilihan yang ada tiap langkahnya.
- Fungsi untuk mengisikan nilai local maximum ke solusi keseluruhan.
- Fungsi yang menentukan apakah solusi telah didapatkan.
Tentunya fungsi-fungsi di atas juga dapat digabungkan atau dipecah lebih lanjut lagi, menyesuaikan dengan strategi greedy yang dikembangkan
Algoritma Divide And Conquer
Sumber : Wikipedia >
Dalam ilmu komputer >> divide and conquer >> algoritma >>didasarkan pada rekursi multi-cabang . Algoritma divide and conquer >> memecah masalah secara rekursif menjadi dua atau lebih sub-masalah dari jenis yang sama atau terkait >> menjadi cukup sederhana untuk diselesaikan secara langsung. Solusi untuk sub masalah kemudian digabungkan untuk memberikan solusi untuk masalah aslinya.
Divide-and-conquer >> dasar dari algoritma yang efisien untuk semua jenis masalah, seperti pengurutan (misalnya, quicksort , jenis penggabungan ), mengalikan angka-angka besar (misalnya algoritma Karatsuba ), menemukan pasangan titik terdekat , analisis sintaksis (misalnya, parser top-down ), dan menghitung transformasi Fourier diskrit ( FFT ). [1]
Memahami dan mendesain algoritma divide-and-conquer >> keterampilan kompleks yang membutuhkan pemahaman yang baik tentang sifat dasar masalah yang akan dipecahkan >> Seperti ketika membuktikan teorema dengan induksi , seringkali masalah asli harus diganti dengan masalah yang lebih umum atau rumit untuk menginisialisasi rekursi, dan tidak ada metode sistematis untuk menemukan generalisasi yang tepat. [ Klarifikasi diperlukan ] Komplikasi divide and conquer ini terlihat saat mengoptimalkan penghitungan bilangan Fibonacci dengan rekursi ganda yang efisien . [ kenapa? ] [ butuh rujukan ]
Kebenaran >> algoritma divide and conquer >> dibuktikan dengan induksi matematis >> sering ditentukan dengan menyelesaikan hubungan pengulangan .
Divide and Conquer
divide-and-conquer >> mengurutkan daftar (38, 27, 43, 3, 9, 82, 10) dalam urutan yang meningkat. Setengah bagian atas: membelah menjadi sublist; mid: daftar satu elemen diurutkan dengan mudah; bagian bawah: menyusun sublist yang diurutkan.
Misalnya, untuk mengurutkan daftar n bilangan asli tertentu, pisahkan menjadi dua daftar yang masing-masing berisi sekitar n / 2, urutkan masing-masing secara bergantian, dan sisipkan kedua hasil dengan tepat untuk mendapatkan versi yang diurutkan dari daftar yang diberikan (lihat gambar). Pendekatan ini dikenal sebagai algoritma pengurutan gabungan .
“divide and conquer” >> kadang >> pada algoritma yang mengurangi setiap masalah menjadi hanya satu sub-masalah >> algoritma pencarian biner - menemukan catatan dalam daftar yang diurutkan (atau analognya dalam komputasi numerik , algoritma pembagian dua untuk root menemukan ). [2] >> dapat diimplementasikan lebih efisien daripada algoritma divide-and-conquer >> menggunakan rekursi ekor , mereka dapat diubah menjadi loop sederhana.
Oleh karena itu, beberapa penulis menganggap bahwa nama “divide and conquer” harus digunakan hanya jika setiap masalah dapat menghasilkan dua atau lebih subproblem. [3] Pengurangan dan penaklukan nama telah diusulkan sebagai gantinya untuk kelas subproblem tunggal. [4]
Historis
Deskripsi yang jelas >> algoritma pada komputer muncul pada tahun 1946 dalam sebuah artikel oleh John Mauchly >> gagasan untuk menggunakan daftar item yang diurutkan untuk memfasilitasi pencarian berasal >> Babylonia pada 200 SM. [5]
Algoritma divide-and-conquer lainnya >> algoritma Euclidean untuk menghitung pembagi persekutuan terbesar dari dua bilangan dengan mengurangi bilangan tersebut >> subproblem ekuivalen yang lebih kecil dan lebih kecil >> beberapa abad SM.
Contoh awal >> algoritma divide and conquer >> deskripsi Gauss pada tahun 1805 tentang apa yang sekarang disebut algoritma Cooley-Tukey fast Fourier transform (FFT), [6] meskipun >> tidak menganalisis jumlah operasinya secara kuantitatif, dan FFT tidak tersebar luas sampai ditemukan kembali lebih dari satu abad kemudian.
D&C dua subproblem awal yang secara khusus dikembangkan untuk komputer dan dianalisis dengan benar >> pengurutan gabungan , yang ditemukan oleh John von Neumann pada tahun 1945. [7]
Contoh lainnya >> algoritma yang ditemukan oleh Anatolii A. Karatsuba pada tahun 1960 [8] yang dapat mengalikan dua angka n-digit dalam operasi (dalam notasi Big O ).
Contoh >> awalnya tidak melibatkan komputer, Donald Knuth memberikan metode >> digunakan kantor pos untuk merutekan surat: surat diurutkan ke dalam tas terpisah untuk wilayah geografis yang berbeda, masing-masing tas ini diurutkan sendiri ke dalam batch untuk sub-wilayah yang lebih kecil, dan seterusnya sampai dikirimkan. [5] Ini terkait dengan jenis radix , dijelaskan untuk mesin sortir kartu berlubang sejak tahun 1929. [5]
Keuntungan
Memecahkan masalah yang sulit
Divide-and-conquer >> alat yang ampuh untuk memecahkan masalah yang sulit secara konseptual >> yang dibutuhkan hanyalah cara memecahkan masalah menjadi sub-masalah, memecahkan kasus-kasus sepele dan menggabungkan sub-masalah ke masalah asli.
Efisiensi algoritma
divide-and-conquer >> membantu dalam penemuan algoritma yang efisien. >> misalnya, untuk metode perkalian cepat Karatsuba, algoritma quick sort dan merge sort, algoritma Strassen untuk perkalian matriks, dan transformasi Fourier cepat.
Paralelisme
Algoritma Divide-and-conquer secara alami diadaptasi >> eksekusi di mesin multi-prosesor, terutama sistem memori bersama di mana komunikasi data antara prosesor tidak perlu direncanakan sebelumnya, karena sub-masalah yang berbeda dapat dijalankan pada prosesor yang berbeda.
Akses memori
Algoritma divide and conquer >> memanfaatkan cache memori secara efisien . Alasannya adalah bahwa setelah sub-masalah cukup kecil, sub-masalah itu dan semua sub-masalah pada prinsipnya dapat diselesaikan dalam cache, tanpa mengakses memori utama yang lebih lambat. Algoritma yang dirancang untuk mengeksploitasi cache dengan cara ini disebut cache-oblivious , karena tidak memuat ukuran cache sebagai parameter eksplisit. [9]
Kontrol pembulatan
Dalam perhitungan dengan aritmatika bulat, misalnya >> bilangan floating-point , algoritma divide and conquer dapat menghasilkan hasil yang lebih akurat daripada metode iteratif yang secara dangkal setara.
Misalnya,
- seseorang dapat menambahkan nomor N >> dengan loop sederhana yang menambahkan setiap datum ke variabel tunggal, atau
- Dengan algoritma D&C >> penjumlahan berpasangan yang memecah kumpulan data menjadi dua bagian, secara rekursif menghitung jumlah setiap setengah, dan kemudian menambahkan dua jumlah. Meskipun metode kedua melakukan jumlah penambahan yang sama seperti yang pertama, dan membayar biaya tambahan dari panggilan rekursif, metode ini biasanya lebih akurat. [10]
Masalah dalam implementasi
Pengulangan
Algoritma divide-and-conquer >> diimplementasikan >> prosedur rekursif >> sebagian sub-masalah yang mengarah ke masalah yang sedang diselesaikan secara otomatis disimpan dalam tumpukan panggilan prosedur.
Tumpukan eksplisit
>> dapat diimplementasikan >> program non-rekursif yang menyimpan sub-masalah parsial dalam beberapa struktur data eksplisit, seperti tumpukan , antrian , atau antrian prioritas .
Ukuran tumpukan
>> implementasi D&C >> harus memastikan >> ada cukup memori yang dialokasikan untuk tumpukan rekursi, jika tidak, eksekusi mungkin gagal karena tumpukan melimpah .
Algoritma D&C yang hemat waktu seringkali memiliki kedalaman rekursi yang relatif kecil. Contoh, algoritma quick sort dapat diimplementasikan sehingga tidak membutuhkan lebih dari panggilan rekursif bersarang untuk mengurutkan item.
Stack overflow >> sulit untuk dihindari saat menggunakan prosedur rekursif, karena banyak compiler berasumsi bahwa stack rekursi adalah area memori yang berdekatan >> mengalokasikan jumlah ruang yang tetap untuk itu.
Memilih kasus dasar
Memilih kasus sederhana mungkin lebih baik >> biasanya mengarah ke program yang lebih sederhana, karena ada lebih sedikit kasus untuk dipertimbangkan dan lebih mudah dipecahkan. Misalnya, algoritma FFT dapat menghentikan rekursi jika inputnya adalah sampel tunggal, dan pengurutan daftar quicksort dapat berhenti jika inputnya adalah daftar kosong; pada kedua contoh hanya ada satu kasus dasar yang perlu dipertimbangkan, dan tidak memerlukan pemrosesan.
>> efisiensi >> meningkat jika rekursi dihentikan pada kasus yang relatif besar, dan ini diselesaikan secara non-rekursif >> hibrid >> menghindari overhead panggilan rekursif.
Berbagi sub masalah yang berulang
>> masalah >> rekursi bercabang >> mengevaluasi sub-masalah yang sama berkali-kali. >> ada baiknya mengidentifikasi dan menyimpan solusi untuk sub masalah yang tumpang tindih >> teknik yang biasa dikenal >> memoization >> mengarah ke algoritma divide-and-conquer bottom-up seperti pemrograman dinamis dan penguraian grafik .
Efisiensi Sistem
Sumber : Edward Huang >
Pada tahun 2004, Google >> model dan Strategi pemrograman >> menggunakan Divide and Conquer Strategy untuk mengoptimalkan algoritma pencariannya.
Jeff dan Sanjay membuat kerangka MapReduce untuk menyederhanakan pemrosesan data >> pengaturan terdistribusi skala besar. Pekerjaan MapReduce biasanya membagi kumpulan data masukan menjadi potongan independen yang diproses oleh mapping secara paralel sepenuhnya - mengurutkan output dari hasil mapping, dan memasukkannya ke tugas pengurangan.
Apache, organisasi >> menggunakan MapReduce untuk mengimplementasikan mesin pencari >> aktif sampai sekarang.
MapReduce >> inovasi teknologi paling penting yang menangani >> skala besar.
Divide and Conquer tidak hanya diimplementasikan dalam >> perangkat lunak >> tetapi juga diadopsi secara luas >> manusia untuk mendapatkan >> mengoptimalkan tugas.
Politisi dan pemimpin menggunakan Devide and Conquer untuk mempertahankan kendali >> kekuasaan. Julius Caesar berkata, " Divida et Impera " >> membagi Roma selain itu >>juga diterapkan >> Seni Perang Sun Tzu
Investor menggunakan Strategi Divide and Conquer >> mengoptimalkan portofolio seseorang. Satu artikel yang diterbitkan di Independent.co menyebutkan bagaimana investor dapat menggunakan kombinasi aset yang terdiversifikasi dengan memahami bagaimana masing-masing aset bekerja di masa lalu untuk menilai proporsi aset yang berbeda.
Menggunakan Divide and Conquer dalam pengaturan yang salah dapat dianggap kejam. Misalnya, seorang manajer dapat menggunakan Strategi Divide and Conquer untuk menetapkan tanggung jawab bersama kepada dua orang yang sudah berselisih.
Pada awalnya, ini mungkin merupakan upaya untuk memberi kedua karyawan kesempatan lain untuk menyelesaikan masalah. Namun, seringkali itu untuk melindungi posisi superior dengan menjaga para pejuangnya dalam konflik. Ini menciptakan lingkungan beracun di tempat kerja yang menyebabkan perputaran karyawan. Lebih baik memupuk kejujuran dan persatuan daripada perpecahan di tempat kerja.
Pencarian/Search
Google banyak membantu >> pengambilan keputusan >>misal : menghabiskan waktu >> mencari di Google sebelum membeli rumah.
Dalam sebuah organisasi, proses pengambilan keputusan yang paling memakan waktu adalah mencari sumber yang tepat dan menganalisisnya.
>> strategi Divide and Conquer >> membantu menyederhanakan dan melakukan pencarian dengan lebih efisien,
Banyak orang secara tidak sadar menggunakan pencarian biner di masa kanak-kanak >> mencari kata di kamus >> tidak akan membuka setiap halaman untuk mencari kata tersebut >> akan mulai mencari kata-kata dari tengah dan mempersempit kumpulan kata yang tersisa untuk diperiksa.
Dalam men-debug masalah, >> membagi kode menjadi dua bagian, dan melihat di mana letak masalahnya. Jika terletak di paruh pertama kode, abaikan separuh lainnya. Bagilah >> bagian pertama >> kode tersebut menjadi bagian yang lain >> lakukan hal yang sama >> menemukan akar masalahnya.
Pinterest akan mengajukan dua pertanyaan pribadi >> mendaftar - usia dan jenis kelamin - dan >> jawaban seseorang >> membentuk segala sesuatu yang terjadi selanjutnya. >> bahasa, wilayah, dan sedikit riwayat Anda, sistem pembelajaran mesin Pinterest akan menggunakan konsep pencarian biner untuk menemukan kategori yang cocok untuk Anda.
Inti dari penggunaan divide and conquer >> tidak perlu membatasi diri >> untuk mencari keseluruhan output dari sistem >> memecahkan masalah.
Sumber : phpmu