Algoritmni optimallashritish usullari
Tags: algorithms, javascript, interview
Published: 2023-07-09 10:00:19

Intervyuda beriladigan masalalarni yechishda avvalambor, _"Brute Force"_, ya'ni unchalik optimal bo'lmagan, lekin ishlaydigan yechim berish kerak. Keyinchalik shu _"Brute Force"_ yechimni qanday qilib optimallashtirish mumkin? Aslida sizni intervyu qiladigan odam ham shuni kutib turadi va ko'p hollarda optimal yechimga olib boradigan ishoralar berishga harakat qiladi.
Buning birinchi usullaridan biri: **"BUD"**.
## BUD usuli
**BUD** - quyidagi so'zlarning bosh harflaridan tuzilgan:
- **B**ottlenecks
- **U**nnecessary work
- **D**uplicated work

---

**"Bottlenecks"** - to'siqlar. Bu algoritm hisoblanishiga ketadigan vaqtni sekinlashtirayotgan qismidir.
Masalan: bizda mavjud ko'p qismli algoritmning 1-qismi berilgan massivni saralasin, 2-qismi esa saralangan massivdan ma'lum bir elementni topsin. Algoritm hisoblanishiga ketadigan vaqt 1-qismda `O(n*log(n))`, 2-qismda `O(n)` bo'lsin. Ko'rinib turibdiki, algorimning 1-qismi algoritm hisoblanish vaqtini sekinlashtiryapti. Agar biz uni optimallashtiradigan bo'lsak, algoritmni optimallashtirgan bo'lamiz.

![O(n) vs O(n*log(n))](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/ped6h72u9w1iiu8h9vp3.png)

**Masala:**
Butun sonlardan tashkil topgan va bo'sh bo'lmagan massiv berilgan bo'lsin. Massivda bir elementdan tashqari har bir element ikki martadan qatnashadi. Takrorlanmagan elementni topish va uni qaytarish kerak.

**Yechish:**
Birinchi bo'lib hayolga keladigan yechim quyidagicha bo'lishi mumkin:
```js
function singleNumber (nums) {
    nums.sort((a, b) => a - b);

    for (let i = 0; i < nums.length; i++) {
        if (nums[i] !== nums[i - 1] && nums[i] !== nums[i + 1]) {
            return nums[i];
        }
    }
};
```
Demak, biz avvalambor berilgan massivimizni o'sish tartibida saralab oldik. JavaScriptning `sort()` metodi `O(n*log(n))` o'rtacha hisoblash vaqtiga ega, bu yerda `n` massiv uzunligidir. Keyingi sikl esa har bir elementni tekshiradi va agar massiv elementi undan oldingi va keyingi elementlarga teng bo'lmasa, shu elementni qaytaradi. Bu sikl `O(n)` chiziqli hisoblash vaqtiga  ega.
Funksiyaning umumiy hisoblash vaqti `O(n*log(n)) + O(n)` bo'lib, `O(n*log(n))`ga soddalashadi. Bu funksiyamizdagi hisoblash vaqtini sekinlashtirayotgan qismi - massivni saralagan qismimizdir. Umuman olganda, bizga massivni saralashimiz kerakmi? Masalani massivni saralamasdan ham yecha olamizmi?

![Thinking meme](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/ha7nac89t4hd5ni6apuf.png)

Endi _"Brute Force"_ yechimimizni optimallashtirishga o'tamiz.
```js
function singleNumber(nums) {
  let singleNum = 0;
  
  for (let num of nums) {
    singleNum ^= num;
  }
  
  return singleNum;
}
```
Ushbu optimallashtirilgan algoritmimizda biz massivning har bir elementini ko'rib chiqyapmiz va bitli _XOR_ operatoridan `^` foydalangan holda `singleNum` o'zgaruvchimizga qo'shib bormoqdamiz. Raqamni o'zi bilan _XOR_ lash 0 qiymatini beradi, shuning uchun takroriy raqamlar mavjud bo'lganda, ular 0 bo'lib ketadi va faqatgina takrorlanmagan raqam qoladi. Bu esa umumiy `O(n)` hisoblash vaqtini oladi.

---

**Unnecessary work** - keraksiz ish. Biz algoritmimizda biror-bir keraksiz ishni amalga oshiryapmizmi?

**Masala:**
Quyidagi ikki xususiyatga ega (m x n) butun sonlar matritsasi berilgan:
- Har bir qator kamaymaydigan tartibda tartiblangan.
- Har bir satrning birinchi butun soni oldingi qatorning oxirgi butun sonidan kattaroqdir.

Masalan:

![Sorted matrix](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/0i4xiprb64booyddgape.jpg)

Butun son `target` berilgan bo'lsa, agar `target` matritsada bo'lsa, `true`, aks holda `false` qaytarish kerak.

**Yechish:**
_"Brute Force"_ yechim quyidagicha bo'lishi mumkin:
```js
function searchMatrix(matrix, target) {
    for(let i = 0; i < matrix.length; i++) {
        for(let j = 0; j < matrix[i].length; j++) {
            if(matrix[i][j] === target) return true;
        }
    }
    return false;
 };
```
Bunda biz matritsani har bir elementini berilgan `target`ga teng yoki teng emasligini tekshirish uchun ichma-ich `for` sikllaridan foydalanyapmiz. Bu algoritmning hisoblash vaqti `O(m*n)`, m - matritsaning qatorlar soni, n - matritsaning ustunlari soni. Aslida, keraksiz ishni amalga oshiryapmiz. Bizga matritsa elementlari ma'lum bir tartibda saralangani haqidagi ma'lumotdan foydalanmayapmiz, ya'ni keraksiz ishni bajaryabmiz.
Matritsaning elementlari ma'lum bir qoida asosida saralangani haqidagi ma'lumotni inobatga olib, biz quyidagi yechimni berishimiz mumkin:
```js
function searchMatrix(matrix, target) {
  const numRows = matrix.length;
  const numCols = matrix[0].length;
  let left = 0;
  let right = numRows * numCols - 1;

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    const midElement = matrix[Math.floor(mid / numCols)][mid % numCols];

    if (midElement === target) {
      return true;
    } else if (midElement < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }

  return false;
}
```
Ma'lumki, saralangan massivdan biror-bir elementni topish uchun _"Binary search"_ algoritmidan foydalanish samaralidir. Ushbu yondashuvda element har doim massivning o'rtasidan qidiriladi. Bizda matritsa bo'lganligi uchun matritsaning o'rta elementini topish hisob-kitoblarimiz biroz boshqacharoq bo'ladi. Agar matritsaning o'rta elementi qidirilayotgan elementdan kichik bo'lsa bizga matritsaning o'rta elementidan chap qismi kerak emas, ularni tashlab yuborsak bo'ladi. Agar matritsaning o'rta elementi qidirilayotgan elementdan katta bo'lsa bizga matritsaning o'rta elementidan o'ng qismi kerak emas, ularni tashlab yuborsak bo'ladi. Shunday yo'l bilan biz matritsadan ma'lum bir elementni qidirishni optimallashtirdik. Bunda algoritm hisoblanishiga ketadigan vaqt `O(log(m*n))`.

---

**Duplicated work** - takroriy ish. Algoritmda biror-bir ishni takroran bajaryapmizmi?

**Masala:**
`n`-chi `fibonacci` sonini qaytaring.

**Yechim:**
```js
function fibonacci(n) {
    if (n <= 1) {
        return n;
    }
    
    return fibonacci(n - 1) + fibonacci(n - 2);
}
```
Ushbu funksiya `fibonacci` sonlar ketma-ketligidan `n`-sonni qaytaradi. Bu sonlar ketma-ketligi - har bir raqam oldingi ikkitasining yig'indisi bo'lgan raqamlar qatoridir. U 0 va 1 dan boshlanadi va keyingi raqamlar oldingi ikkita raqamni qo'shish orqali hosil bo'ladi. Masalan:
`0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...`
Biroq, buni amalga oshirishda, funktsiya bir xil `fibonacci` raqamlarini bir necha marta qayta-qayta hisoblab chiqadi, ya'ni takroriy ishni bajaryapmiz. Algoritm hisoblanishiga ketadigan vaqt `O(2^n)`. Uni qanday optimallashtirishimiz mumkin?

![Thinking meme](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/6u43qr7m4qewbra42tu0.png)

Biz qo'shimcha xotiradan foydalanishimiz mumkin:
```js
function fibonacci(n) {
    let memo = {};
    return fibonacciHelper(n, memo);
}

function fibonacciHelper(n, memo) {
    if (n <= 1) {
        return n;
    }
    
    if (memo[n]) {
        return memo[n];
    }
    
    memo[n] = fibonacciHelper(n - 1, memo) + fibonacciHelper(n - 2, memo);
    return memo[n];
}
```
`fibonacciHelper` funksiyasi argument sifatida `n` va `memo`ni qabul qiluvchi rekursiv yordamchi funksiyadir. `fibonacciHelper` funktsiyasi ichida biz  berilgan `n` uchun `fibonacci` raqami `memo` ob'ektida mavjudligini tekshiramiz. Agar u mavjud bo'lsa, biz `memo` ob'ektidan oldindan hisoblangan qiymatni qaytaramiz. Agar `fibonacci` raqami `memo` ob'ektida mavjud bo'lmasa, u `fibonacci` raqamini rekursiv hisoblab chiqadi. Hisoblangan `fibonacci` raqami keyinchalik ma'lumot sifatida `memo` ob'ektida saqlanadi va qaytariladi.
Qo'shimcha xotiradan foydalangan holda oldindan hisoblangan `fibonacci` raqamlarini saqlash orqali takroriy ishlarni oldini olamiz. Bu `fibonacci` hisobining samaradorligini sezilarli darajada yaxshilaydi. Algoritm hisoblanishiga ketadigan vaqt `O(n)`. Bu yaxshilanishga avvaldan hisoblangan `fibonacci` raqamlarini saqlash yordamida ortiqcha hisob-kitoblarni yo‘q qilish orqali erishildi.

---

## Xulosa:
**BUD** optimallashtirish usuli - "to'siqlar, keraksiz ish va takroriy ish" degan ma'noni anglatadi va algoritmlar yoki kodlardagi samarasizlikni aniqlash va bartaraf etish uchun ishlatiladigan printsipdir. Ushbu usul _"Brute Force"_ yechimini ishlab chiqqandan keyingi birinchi variantlardan biri bo'lishi kerak. Chunki u algoritmning hisoblash vaqtini yaxshilash usullarini aniqlashga qaratilgandir.