jenis jenis algoritma

Jenis Jenis Algoritma

Kecepatan algoritma diukur dari segi jumlah operasi dasar itu melakukan.
Pertimbangkan sebuah algoritma yang mengambil N sebagai masukan dan melakukan berbagai operasi.
Korelasi antara jumlah operasi yang dilakukan dan waktu yang dibutuhkan untuk menyelesaikan adalah sebagai berikut-
(Menganggap N 1.000 dan kecepatan prosesor sebagai 1 Ghz)
Masalah yang waktu berjalan tidak tergantung pada waktu konstan masukan size--. (sangat kecil)

log N operasi --- 10 ns

N operasi --- 1 us

N*log N operasi ---- 20 us

N! operasi ---- waktu tak terbayangkan.

Oleh karena itu, perlu dicatat bahwa setiap algoritma berada di bawah kelas tertentu. Dari rangka meningkatkan klasifikasikan sebagai algoritma waktu konstan, algoritma logaritmik, algoritma waktu linear, algoritma waktu polinomial dan algoritma waktu eksponensial.
Secara formal, kami menunjukkan kompleksitas algoritma menggunakan asimtotik notasi Ө (n) [baca Theta dari n]

Pada dasarnya ada 3 notasi asymptotic digunakan. Ө (theta), O (Big O), Ω (omega).
Secara matematis, ini didefinisikan sebagai berikut:

Untuk suatu fungsi g (n), kita dilambangkan dengan Θ (g (n)) set fungsi
Θ (g (n)) = {f (n): terdapat konstanta positif c1, c2, dan n0 sehingga 0 ≤ c1g (n) ≤ f (n) ≤ C2G (n) untuk semua n ≥ n0}.
Untuk suatu fungsi g (n), kita dilambangkan dengan O (g (n)) set fungsi
O (g (n)) = {f (n): terdapat konstanta positif c dan n0 sehingga 0 ≤ f (n) ≤ cg (n) untuk semua n ≥ n0}.
Untuk suatu fungsi g (n), kita dilambangkan dengan Ω (g (n)) set fungsi
Ω (g (n)) = {f (n): terdapat konstanta positif c dan n0 sehingga 0 ≤ cg (n) ≤ f (n) untuk semua n ≥ n0}.

Jadi apa artinya ini?
Informal, O (g (n)) menetapkan suatu batas atas pada fungsi. Ini digunakan untuk menunjukkan runtime kasus terburuk dari algoritma.
Θ (g (n)) mendefinisikan dua fungsi yang terikat fungsi g (n) dari kedua atas dan bawah untuk nilai-nilai yang sesuai untuk konstanta c1, c2, n0. Ini digunakan untuk menunjukkan runtime rata-rata algoritma.
Ω (g (n)) mendefinisikan batas bawah dari fungsi. Kita bisa menggunakannya untuk menunjukkan runtime kasus Terbaik dari suatu algoritma.
Kami akan menggunakan notasi ini untuk menunjukkan kompleksitas waktu dari algoritma yang akan dibahas kemudian.

Berbagai jenis algoritma: -
Setiap algoritma berada di bawah kelas tertentu. Pada dasarnya ialah-

1) Brute force (kekerasan)
2) Divide and conquer (Membagi dan menaklukkan)
3) Decrease and conquer (Penurunan dan menaklukkan)
4) Dynamic programming (pemrograman dinamis)
5) algoritma Greedy
6) Transform and conquer
7) algoritma Backtracking

Algoritma brute force: -
brute force menyiratkan menggunakan definisi untuk memecahkan masalah dengan cara langsung.
algoritma brute force biasanya yang paling mudah untuk melaksanakan, tetapi kelemahan dari pemecahan masalah dengan brute force adalah bahwa hal itu biasanya sangat lambat dan dapat diterapkan hanya untuk masalah di mana ukuran input kecil.

algoritma Divide dan conquer: -
membagi(devide):
Masalahnya dibagi menjadi beberapa sub-masalah.
Menaklukkan (conquer):
sub-masalah yang dibandingkan diselesaikan secara rekursif. Jika ukuran sub-masalah yang cukup kecil, hanya memecahkan sub-masalah secara langsung.
Menggabungkan(combine):
dalam langkah ini, solusi dari sub-masalah yang dibandingkan digabungkan menjadi solusi untuk masalah asli.
Dalam membagi dan metode menaklukkan, kita membagi ukuran masalah dengan faktor konstan dalam setiap iterasi. Ini berarti kita harus memproses lebih rendah dan lebih rendah bagian dari masalah asli dalam setiap iterasi. Beberapa algoritma tercepat milik kelas ini. Algoritma Divide dan conquer memiliki runtime logaritmik.

algoritma Decrease dan conquer: -
masalah seperti ini adalah sama dengan devide dan conquer, kecuali, di sini kita mengurangi masalah dalam setiap iterasi oleh ukuran konstan, bukan faktor konstan.

Algoritma pemrograman dinamis: -
Pengembangan algoritma pemrograman dinamis dapat dipecah menjadi urutan empat langkah.

1.      Karakterisasi struktur suatu solusi optimal.

2.      Secara rekursif menentukan nilai solusi optimal.

3.      Menghitung nilai dari solusi optimal dalam bottom up fashion.

4.      Menyusun suatu solusi optimal dari informasi komputer.

Kata 'dinamis' mengacu pada metode di mana algoritma menghitung hasilnya. Kadang-kadang, solusi untuk contoh yang diberikan dari masalah tergantung pada solusi untuk contoh kecil dari sub-masalah. Ini menunjukkan tumpang tindih sub-masalah. Oleh karena itu, untuk memecahkan masalah kita mungkin harus menghitung ulang nilai-nilai yang sama secara berulang untuk yang lebih kecil sub-masalah. Oleh karena itu, siklus komputasi yang terbuang.
Untuk memperbaiki hal ini, kita dapat menggunakan teknik pemrograman dinamis. Pada dasarnya, dalam pemrograman dinamis, kami "ingat" hasil dari masing-masing sub-masalah. Setiap kali kita membutuhkannya, kita akan menggunakan nilai yang bukan recomputasi lagi.
Di sini, kita menggunakan lebih banyak ruang untuk memegang nilai-nilai dihitung untuk meningkatkan kecepatan eksekusi drastis.
Sebuah contoh yang baik untuk masalah yang telah tumpang tindih overlap sub-masalah adalah relasi untuk nomor N Fibonacci.
Hal ini didefinisikan sebagai F (n) = F (n-1) + F (n-2).
Perhatikan bahwa jumlah N Fibonacci tergantung pada sebelumnya dua angka Fibonacci.
Jika kita menghitung F (n) dengan cara konvensional, kita harus menghitung dengan cara berikut
Nilai berwarna serupa adalah data yang akan dihitung secara berulang. Perhatikan bahwa F (n-2) dihitung 2 kali, F (n-3) 3 kali dan seterusnya ... Oleh karena itu, kita membuang-buang banyak waktu. Dalam Fakta, rekursi ini akan melakukan [Math Processing Error] operasi untuk N yang diberikan, dan itu sama sekali tidak dipecahkan untuk N> 40 pada PC modern dalam setidaknya satu tahun.

Solusi untuk ini adalah untuk menyimpan setiap nilai seperti yang kita menghitung dan mengambilnya langsung, bukan menghitung ulang. Ini mengubah algoritma waktu eksponensial dalam algoritma waktu linear.
Oleh karena itu, pemrograman dinamis adalah teknik yang sangat penting untuk mempercepat masalah yang telah tumpang tindih sub masalahnya.

Algoritma Greedy (algoritma serakah): -
langkah-langkah berikut yang terlibat dalam algoritma greedy

1.      Menentukan struktur optimal dari masalah.

2.      Mengembangkan solusi rekursif.

3.      Buktikan bahwa pada setiap tahap rekursi, salah satu pilihan yang optimal adalah pilihan greedy, dengan demikian, selalu aman untuk membuat pilihan yang greedy.

4.      Menunjukkan bahwa semua kecuali satu dari sub-masalah yang disebabkan oleh telah pilihan yang greedy kosong.

5.      Mengembangkan algoritma rekursif yang mengimplementasikan strategi greedy.

6.      Mengkonversi algoritma rekursif untuk algoritma iteratif.

Bagi banyak masalah, membuat pilihan greedy mengarah ke solusi optimal. algoritma ini berlaku untuk permasalahan optimasi.
Dalam algoritma greedy, di setiap langkah, kita akan membuat solusi lokal optimal sehingga hal itu akan menyebabkan solusi global optimal. Setelah pilihan dibuat, kita tidak bisa menarik kembali di tahap-tahap selanjutnya.
Membuktikan kebenaran algoritma greedy sangat penting, karena tidak semua algoritma greedy menyebabkan secara global solusi optimal.
Untuk contohnya dimana kita mempertimbangkan masalah di mana Anda diberi koin denominasi (pecahan)tertentu dan diminta untuk membangun sejumlah uang di jumlah minimum koin.
Biarkan koin menjadi 1, 5, 10, 20 cents
Jika kita ingin mengubah untuk 36 cents, kita pilih koin mungkin terbesar pertama (pilihan greedy).
Menurut proses ini, kita pilih koin sebagai berikut:

20
20 + 10
20 + 10 + 5
20 + 10 + 5 + 1 = 36.

Untuk koin dari denominasi(pecahan)  tertentu, algoritma greedy selalu bekerja.
Tapi secara umum hal ini tidak benar.
Pertimbangkan pecahan sebagai 1, 3, 4 cent
Untuk membuat 6 cent, menurut algoritma greedy koin yang dipilih adalah 4 + 1 + 1
Tapi, koin minimal yang dibutuhkan hanya 2 (3 + 3)
Oleh karena itu, algoritma greedy bukanlah pendekatan yang benar untuk memecahkan masalah 'perubahan pembuatan'.
Dalam Fakta, kita dapat menggunakan pemrograman dinamis untuk sampai pada solusi optimal untuk masalah ini.

Algoritma Transform dan conquer:-
Kadang-kadang sangat sulit atau tidak begitu jelas bagaimana untuk sampai pada solusi untuk masalah tertentu.
Dalam hal ini, lebih mudah untuk mengubah masalah menjadi sesuatu yang kita kenali, dan kemudian mencoba untuk memecahkan masalah yang tiba di solusi.
Mempertimbangkan masalah untuk menemukan LCM dari sebuah nomor. pendekatan brute force mencoba setiap nomor dan melihat jika itu adalah LCM bukan pendekatan yang terbaik. Sebaliknya, kita dapat menemukan masalah GCD menggunakan algoritma yang sangat cepat yang dikenal sebagai algoritma Euclid dan kemudian menggunakan hasil bahwa untuk menemukan LCM sebagai LCM (a, b) = (a * b) / GCD (a, b)

Algoritma Backtracking: -
Pendekatan Backtracking ini sangat mirip dengan pendekatan brute force. Namun perbedaan antara backtracking dan brute force adalah bahwa, dalam pendekatan brute force, kita menghasilkan setiap kemungkinan kombinasi solusi dan menguji apakah itu adalah solusi yang valid. Padahal, di backtracking, setiap kali Anda menghasilkan solusi, Anda menguji jika memenuhi semua kondisi, dan hanya kemudian kita terus menghasilkan solusi berikutnya, yang lain kita akan mundur dan berada pada jalan yang berbeda untuk menemukan solusi.
Sebuah contoh yang terkenal untuk masalah ini adalah masalah N Queens. Menurut masalah, kita diberi N X N berukuran papan catur. Kita harus menempatkan N ratu pada papan catur sehingga tidak ada ratu berada di bawah serangan dari setiap queen lainnya.

Kami melanjutkan dengan menempatkan seorang ratu di setiap kolom dan baris yang sesuai. Setiap kali kita menempatkan Ratu, kita cek apakah itu diserang. Jika demikian, maka kita akan memilih sel yang berbeda di bawah kolom tersebut. Anda dapat memvisualisasikan proses seperti pohon. Setiap node di pohon adalah papan catur dari konfigurasi yang berbeda. Pada tahap apapun jika kami tidak dapat melanjutkan, maka kita mundur dari simpul itu dan melanjutkan dengan memperluas node lain.

Keuntungan dari metode ini lebih brute force adalah bahwa jumlah calon yang dihasilkan sangat kurang dibandingkan dengan pendekatan brute force. Oleh karena itu kita dapat mengisolasi solusi valid cepat.
contohnya untuk papan catur 8 X 8, jika kita mengikuti pendekatan brute force, kita harus menghasilkan 4426165368 solusi dan menguji masing-masing. Padahal, di backtracking pendekatan, itu akan dikurangi menjadi 40.320 solusi.

Aplikasi dari jenis algoritma

Permasalahan jaringan (Networking problem)
Katakanlah Anda memiliki jaringan dengan banyak PC yang terhubung dengan cara berikut.
Di sini, setiap node mewakili PC dan nomor pada setiap link merupakan biaya yang diperlukan untuk mempertahankan link tersebut.
Tugas kita adalah untuk meminimalkan biaya dan masih memiliki jalur dari node ke node yang diberikan lainnya.
Cara yang baik untuk mengatasi ini adalah untuk menjadi "Greedy".
Salah satu algoritma greedy untuk memecahkan masalah ini untuk menemukan Minimum Spanning Tree adalah algoritma Kruskal.
Menurut algoritma ini, Dalam setiap iterasi, pilih jalur biaya setidaknya seperti bahwa pemilihan tidak akan membuat siklus cycle. Sebuah pohon, seperti yang Anda tahu, tidak dapat memiliki siklus apapun. Terdapat jalur yang unik antara setiap 2 node yang diberikan.
Jadi, menurut algoritma ini, jika Anda terus memilih jalur biaya setidaknya di setiap iterasi Anda akan berakhir membuat pilihan berikut.

Catatan pada langkah 6 bahwa meskipun link yang paling berikutnya adalah link di bawah label 6, kami tidak memilihnya karena akan menciptakan siklus.
algoritma berakhir ketika kita menemukan N-1 dipinggirnyai di mana N adalah jumlah node.
Oleh karena itu, tree merentang minimum adalah
Menggunakan algoritma greedy, Anda telah meminimalkan biaya untuk meletakkan jaringan dan masih mempertahankan konektivitas antara setiap PC.

Teman yang Paling Populer
Ada masalah lain yang datang di dalam kontes pemrograman.
Menurut masalah ini: - Kami merencanakan acara, dan kami ingin orang sebanyak mungkin untuk menghadiri acara tersebut.
Salah satu cara untuk menyebarkan informasi acara adalah untuk posting di beranda profil facebook. Tapi kita tidak ingin spam dinding semua orang dengan posting. Jadi, kami memutuskan untuk mengetahui teman yang paling populer di grup dan posting kepria / wanitanya dinding nya sehingga ia dapat menyebarkan informasi kepada orang lain.
Di sini, seorang teman populer didefinisikan sebagai seseorang yang dimana jarak ke semua orang lain adalah minimal maksudnya jarak orang yang paling terdekat. Jarak dari orang X ke orang Y adalah jumlah profil Anda harus melompat untuk mencapai Y.

Kami mewakili informasi ini dalam format yang dikenal sebagai matriks adjacency (matriks ketetanggaan).

Berikut, A adalah teman dari B, C, D.
B adalah teman dari A, D.
C adalah teman dari A, D, E.
D adalah teman dari A, C, B, F.
E adalah teman dari C.
F adalah teman dari D.

Oleh karena itu, untuk jarak A dari E adalah 2, dan jarak dari F dari E adalah 3.
Tugas kita adalah untuk menghitung jarak terpendek dari setiap node ke setiap node lain.
ada algoritma pemrograman dinamis untuk melakukan hal ini. Hal ini disebut algoritma Floyd.
Asumsikan bahwa kami mewakili grafik sebagai sebuah matriks.
Di sini, INFINITE berarti bahwa tidak ada jalur langsung antara yang sesuai node diberi label dengan baris-kolom, dan 1 berarti ada jalur langsung antara node.

Jadi, apa prinsip di balik algoritma Floyd?
Pertimbangkan satu set node dalam grafik berlabel 1 N. Asumsikan bahwa kita harus menemukan jalan terpendek dari simpul X ke simpul Y hanya menggunakan node 1 ke K sebagai node intermediate.

Ada ada 2 kemungkinan calon untuk solusi ini.
1) Jalur yang berlangsung dari i ke j hanya menggunakan node 1 ke K sebagai node perantara, seperti yang diasumsikan di atas.
2) Jalur yang berlangsung dari 1 sampai K + 1 dan kemudian pergi dari K + 1 ke tujuan.
Solusi kami adalah salah satu mana yang terpendek.
Jadi, relasi pengulangan kami
Jalur (X, Y, K) = minimum (jalur (X, Y, K-1), jalur (X, K, K-1) + jalur (K, Y, K-1))
Jika Anda perhatikan dengan seksama, kita menghitung sesuatu secara berulang.
jika definisikan panjang dari node X ke node Y menggunakan K node intermediate dalam hal panjang dari X ke Y menggunakan K-1 antara node atau X ke K + 1, K + 1 ke  J, mana yang terpendek

Dan bukan menghitung hal-hal ini berulang kali di setiap langkah, kita dapat menghitung nilai-nilai secara bottom-up dan menyimpannya terlebih dahulu dan mengambilnya secara bertahap kemudian dan menggunakannya untuk perhitungan kita.
Mengkonversi ini menjadi pendekatan pemrograman dinamis. algoritma ini adalah sebagai berikut: -
Algoritma untuk menghitung jalur terpendek dari setiap node ke setiap node yang lain
Input: Sebuah matriks adjacency mendefinisikan jarak antara node.
Output: Sebuah grafik adjacency jalur indikasi terpendek dari setiap node ke setiap node lain.

For K=1 to N

For I=1 to N

For J=1 to N

teman [I] [J] = min (teman [I] [J], teman [I] [K] + teman [K] [J])
Kembali (teman)

algoritma terminate
Algoritma ini memiliki kompleksitas waktu dari Ө (N ^ 3) dan setelah N ^ 3 berlalu, teman array berisi jalur terpendek dari setiap node ke setiap node lain.
Setelah menjalankan ini pada contoh di atas, kita akan mendapatkan hasil sebagai berikut.

Sekarang, kita tahu jarak dari setiap orang untuk setiap orang lain. Jadi yang harus kita lakukan adalah, menemukan jumlah untuk semua orang dan menemukan sedikitnya.

A = 0 + 1 + 1 + 1 + 2 + 2 = 7
B = 1 + 0 + 2 + 1 + 3 + 2 = 9
C = 1 + 2 + 0 + 1 + 1 + 2 = 7
D = 1 + 1 + 1 + 0 + 2 + 1 = 6
E = 2 + 3 + 1 + 2 + 0 + 3 =11
F = 2 + 2 + 2 + 1 + 3 + 0 = 10

D adalah yang paling dekat dengan semua dengan jarak total 6. Oleh karena itu, D adalah teman paling populer dari grup.
Oleh karena itu, cukup jika kita posting undangan kita di dinding D.