Aho-Korasik algoritmi va Shiber-Vishkin algoritmi ning strukturasini o‘rganish va ularning murakkabligini baholash
![Vaqt murakkabligi : O(2^n), chunki har bir chaqiruv ikkita chaqiruvni yaratadi.
Xotira murakkabligi : O(n), rekursiv stackning balandligi n bo‘ladi.
2. Dinamik Dasturlash Algoritmlari
Dinamik dasturlash (DP) — bu masalani kichik subproblemlarga bo‘lib, har bir
subproblemning yechimini saqlash va keyin uni ishlatish usulidir. Bu usul
rekursiyani optimallashtirish orqali samaradorlikni oshiradi.
Dinamik dasturlash misoli: Fibbonachchi sonlari
Fibbonachchi sonlarini dinamik dasturlash yordamida hisoblash:
#include <iostream>
#include <vector>
using namespace std;
// Dinamik dasturlash orqali Fibbonachchi sonini hisoblash
int fibonacci(int n) {
// Fibbonachchi sonlarini saqlash uchun massiv
vector<int> fib(n + 1);
fib[0] = 0; // Fibbonachchi soni 0
fib[1] = 1; // Fibbonachchi soni 1
// Har bir fib(i) sonini hisoblash
for (int i = 2; i <= n; i++) {
fib[i] = fib[i - 1] + fib[i - 2];
}
return fib[n]; // N-chi fibonachchi soni
}
int main() {
int n = 10; // Fibbonachchi sonining 10-chi elementini hisoblash
cout << "Fibbonachchi sonining " << n << "-chi elementi: " << fibonacci(n) <<
endl;](https://docx.uz/documents/576a6420-bcae-4c94-ba73-cf310944d4f1/page_10.png?v=1)
![return 0;
}
Izohlar:
Dinamik dasturlash da, har bir Fibbonachchi soni bir marta hisoblanadi va
saqlanadi. Bu ortiqcha hisoblashlarni oldini oladi.
Vektor yordamida barcha Fibbonachchi sonlari saqlanadi.
Murakkablik:
Vaqt murakkabligi : O(n), har bir fib(i) soni faqat bir marta hisoblanadi.
Xotira murakkabligi : O(n), barcha fib(i) qiymatlari saqlanadi.
3. Dinamik Dasturlash: Eng uzun ortib boruvchi subsequence (LIS)
Endi eng uzun ortib boruvchi subsequence (LIS) masalasini yechish uchun
dinamik dasturlashni ko‘rib chiqamiz. Bu masalani yechishda har bir elementni
oldingi elementlar bilan solishtirib, ortib boruvchi subsequence uzunligini
hisoblaymiz.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// Eng uzun ortib boruvchi subsequence (LIS) funksiyasi
int lis(const vector<int>& arr) {
int n = arr.size();
vector<int> dp(n, 1); // dp massivini boshlang'ich qiymatlari 1
// Har bir element uchun ortib boruvchi subsequence uzunligini hisoblash
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (arr[i] > arr[j]) {
dp[i] = max(dp[i], dp[j] + 1);
}](https://docx.uz/documents/576a6420-bcae-4c94-ba73-cf310944d4f1/page_11.png?v=1)
![// To'xtash sharti
if (n == 1) {
return 1;
}
int max_len = 1;
// Har bir elementni tekshirish
for (int i = 1; i < n; i++) {
if (arr[i - 1] < arr[n - 1]) {
max_len = max(max_len, lis_recursive(arr, i) + 1);
}
}
return max_len;
}
int main() {
vector<int> arr = {10, 22, 9, 33, 21, 50, 41, 60, 80};
int n = arr.size();
cout << "Eng uzun ortib boruvchi subsequence uzunligi: " << lis_recursive(arr, n)
<< endl;
return 0;
}
Izohlar:
Rekursiv yondashuv : Bu usulda har bir elementni oldingi elementlar bilan
solishtiramiz va ortib boruvchi subsequence uzunligini rekursiv chaqiruv orqali
hisoblaymiz.
To‘xtash sharti : Agar n == 1 bo‘lsa, rekursiya to‘xtaydi.
Murakkablik:
Vaqt murakkabligi : O(2^n), rekursiv chaqiruvlar yuqori darajada takrorlanadi.
Xotira murakkabligi : O(n), rekursiv stackning balandligi n bo‘ladi.](https://docx.uz/documents/576a6420-bcae-4c94-ba73-cf310944d4f1/page_13.png?v=1)
![Xulosa
Rekursiv algoritmlar oddiy va intuitiv bo‘lishi mumkin, lekin samaradorlik past
bo‘lishi mumkin, chunki subproblemalar qayta-qayta hisoblanadi.
Dinamik dasturlash esa rekursiyani optimallashtirishga yordam beradi,
subproblemalar faqat bir marta hisoblanadi va natijalar saqlanadi. Bu usul ko‘proq
samarali.
Har ikki yondashuvning murakkabligi va ishlash samaradorligini hisobga olgan
holda, mos masalalar uchun to‘g‘ri yondashuvni tanlash zarur.
1. Brute Force algoritmi
Brute Force algoritmi — bu masalani yechishning eng oddiy va to‘liq usuli bo‘lib,
har bir mumkin bo‘lgan variantni tekshirishni o‘z ichiga oladi. Bu yondashuvda
har bir mumkin bo‘lgan yechim o‘rganiladi, bu esa juda ko‘p vaqt talab qilishi
mumkin.
Brute Force algoritmi misoli: Maksimal elementni topish
Masala : Berilgan massivdagi maksimal elementni topish.
C++ kodi:
#include <iostream>
#include <vector>
using namespace std;
// Brute Force algoritmi orqali maksimal elementni topish
int findMax(const vector<int>& arr) {
int maxVal = arr[0];
for (int i = 1; i < arr.size(); i++) {
if (arr[i] > maxVal) {
maxVal = arr[i];
}
}
return maxVal;](https://docx.uz/documents/576a6420-bcae-4c94-ba73-cf310944d4f1/page_14.png?v=1)
![if (board[row][i] == 1) {
return false;
}
}
// Chap yuqori diagonali tekshirish
for (int i = row, j = col; i >= 0 && j >= 0; i--, j--) {
if (board[i][j] == 1) {
return false;
}
}
// O'ng yuqori diagonali tekshirish
for (int i = row, j = col; j >= 0 && i < n; i++, j--) {
if (board[i][j] == 1) {
return false;
}
}
return true;
}
bool solveNQueens(vector<vector<int>>& board, int col, int n) {
// Agar barcha malikalarga joy berilgan bo'lsa, yechimni topdik
if (col >= n) {
return true;
}
// Har bir qatorni tekshirish
for (int i = 0; i < n; i++) {
if (isSafe(board, i, col, n)) {](https://docx.uz/documents/576a6420-bcae-4c94-ba73-cf310944d4f1/page_16.png?v=1)
![board[i][col] = 1; // Malika joylashdi
// Rekursiv chaqiruv
if (solveNQueens(board, col + 1, n)) {
return true;
}
// Orqaga qaytish (Backtrack)
board[i][col] = 0; // Malika o‘chiriladi
}
}
return false; // Agar hech qanday joylashuv bo'lmasa
}
void printBoard(const vector<vector<int>>& board, int n) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cout << (board[i][j] ? "Q " : ". ");
}
cout << endl;
}
}
int main() {
int n = 4;
vector<vector<int>> board(n, vector<int>(n, 0));
if (solveNQueens(board, 0, n)) {
printBoard(board, n);
} else {
cout << "Yechim mavjud emas!" << endl; }
return 0;](https://docx.uz/documents/576a6420-bcae-4c94-ba73-cf310944d4f1/page_17.png?v=1)
Aho-Korasik algoritmi va Shiber-Vishkin algoritmi ning strukturasini o‘rganish va ularning murakkabligini baholash