Struktur data dan algoritma | Algoritma | DSA

Dalam sains komputer, algoritma selalunya dikategorikan berdasarkan fungsi dan struktur datanya. Berikut ialah pecahan jenis algoritma asas mengikut fungsi terasnya:

1. Algoritma Pencarian

Algoritma ini membantu mencari item tertentu dalam struktur data, seperti tatasusunan atau senarai.

Carian Linear: Semak setiap elemen secara berurutan sehingga sasaran ditemui.

Carian Perduaan: Mencari tatasusunan yang diisih dengan cekap dengan membahagikan selang carian secara berulang kepada separuh.

Carian Lompat: Melangkau ke hadapan dalam tatasusunan yang diisih dan kemudian melakukan carian linear dalam segmen.

Carian Interpolasi: Digunakan pada tatasusunan tersusun yang diedarkan secara seragam; menganggarkan kedudukan kunci carian.

1. Isih Algoritma

Algoritma ini menyusun semula elemen dalam urutan tertentu, biasanya menaik atau menurun.

Isih Buih: Berulang kali menukar elemen bersebelahan jika unsur tersebut berada dalam susunan yang salah.

Isih Pilihan: Mencari elemen terkecil dan mengalihkannya ke bahagian senarai yang diisih.

Isih Sisipan: Membina senarai diisih dengan memasukkan setiap elemen di tempatnya yang sepatutnya.

Isih Gabung: Menggunakan pendekatan bahagi-dan-takluk untuk membahagi, mengisih dan menggabungkan senarai.

Isih Pantas: Bahagikan senarai menggunakan pangsi dan isih subarray secara rekursif.

1. Algoritma Pokok

Algoritma pokok digunakan untuk menavigasi, memanipulasi atau mencari dalam struktur data pokok.

Binary Tree Traversal: Teknik seperti in-order, pre-order dan post-order traversal untuk melawati nod dalam urutan tertentu.

Pokok Carian Perduaan (BST): Pepohon perduaan di mana setiap nod mempunyai anak kiri (lebih kecil) dan kanan (lebih besar).

Pokok AVL: Pepohon carian binari pengimbangan diri.

Pokok Merah-Hitam: BST seimbang yang mengikut peraturan warna tertentu untuk mengimbangi.

Pokok Segmen: Digunakan untuk pertanyaan julat dan kemas kini.

1. Algoritma Graf

Algoritma ini beroperasi pada graf, yang terdiri daripada nod (bucu) dan tepi.

Depth-First Search (DFS): Teroka sejauh mungkin di sepanjang setiap cawangan sebelum menjejak ke belakang.

Breadth-First Search (BFS): Teroka semua jiran sebelum melangkah ke peringkat seterusnya.

Algoritma Dijkstra: Mencari laluan terpendek antara nod dalam graf berwajaran.

Algoritma Bellman-Ford: Mencari laluan terpendek tetapi berfungsi walaupun dengan graf dengan pemberat negatif.

Algoritma Floyd-Warshall: Mengira laluan terpendek antara semua pasangan nod.

1. Algoritma Pengaturcaraan Dinamik

Pengaturcaraan dinamik (DP) digunakan untuk menyelesaikan masalah yang kompleks dengan memecahkannya kepada submasalah yang bertindih.

Jujukan Fibonacci: Mengira nombor Fibonacci ke-n menggunakan pendekatan bawah ke atas.

Masalah Knapsack: Menyelesaikan masalah pengoptimuman untuk peruntukan sumber.

Turutan Sepunya Terpanjang (LCS): Mencari urutan terpanjang sepunya kepada dua rentetan.

Pendaraban Rantaian Matriks: Menentukan cara optimum untuk mendarab matriks.

1. Algoritma Tamak

Algoritma tamak membuat pilihan tempatan terbaik pada setiap langkah untuk mencari optimum keseluruhan.

Algoritma Prim: Mencari pokok rentang minimum untuk graf.

Algoritma Kruskal: Juga mencari pokok rentang minimum dengan menambahkan tepi kos terendah.

Pengekodan Huffman: Memampatkan data dengan membina pepohon binari dengan kod terpendek untuk simbol yang paling biasa.

Pemilihan Aktiviti: Memilih bilangan maksimum aktiviti yang tidak bertindih dalam masa.

1. Algoritma Penjejakan Belakang

Algoritma ini mencuba penyelesaian secara berperingkat-peringkat dan mundur apabila ia menemui jalan buntu.

Masalah N-Queens: Meletakkan N queens pada papan N×N tanpa konflik.

Sudoku Solver: Menggunakan pendekatan menjejak ke belakang untuk mengisi grid teka-teki.

Maze Solver: Cari laluan dalam mez dengan meneroka setiap kemungkinan.

1. Bahagi dan Takluk Algoritma

Bahagi dan takluk algoritma menyelesaikan masalah dengan memecahkannya kepada submasalah yang lebih kecil.

Isih Gabung: Bahagikan senarai kepada dua, isi setiap separuh dan gabungkannya.

Isih Pantas: Bahagikan senarai di sekeliling pangsi.

Carian Perduaan: Membahagikan selang carian untuk mencari sasaran dalam masa logaritma.

Setiap kategori ini menawarkan pendekatan yang berbeza untuk mengendalikan pelbagai jenis masalah pengiraan, menjadikannya lebih mudah untuk memilih algoritma yang betul untuk tugas tertentu.

Atas ialah kandungan terperinci Struktur data dan algoritma | Algoritma | DSA. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!