"Big O" haqida gaplashamiz
Tags: algorithms, javascript, programming, tutorial
Published: 2023-07-05 05:03:04

## Big O - nima?
**Big O** - bu yozilgan algoritm qanchalik samaradorligini aniqlovchi o'lchov. Bu o'lchov algoritmga kiruvchi qiymatlar o'sib borishi bilan algoritm hisoblanishiga ketadigan vaqt yoki maydon qanday o'zgarishini taqribiy ko'rsatadi.

**O(1)** - algoritmga kiruvchi qiymatlar o'sib borsa ham, algoritm hisoblanishiga ketadigan vaqt yoki maydon o'zgarmasdan qolishini anglatadi.

![O(1)](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/24y6gxcytis8qeedtdmc.png)

```
function addValues(a, b) {
  return a + b;
}
```
Ushbu `addValues` funksiyasi `a` va `b` o'zgaruvchilarini kiruvchi qiymatlar sifatida oladi va ularning yig'indisini qaytaradi. `a` va `b` o'zgaruvchilarining qiymati ortib borishi algoritm hisoblanishiga ketadigan vaqtga hech qanday ta'sir qilmaydi. Shuning uchun ushbu algoritm hisoblanishiga `O(1)` vaqt talab qilinadi, hech qanday qo'shimcha joy ishlatilinmaganligi sababli algoritm talab qiladigan joy ham `O(1)`.

---

**O(n)** - algoritmga kiruvchi qiymatlar o'sib borishi bilan algoritm hisoblanishiga ketadigan vaqt yoki maydon ham birdek o'sib borishini anglatadi.
Masalan: Agar biz algoritmda `n` o'lchamdagi massiv yaratsak, algoritm `O(n)` joy talab qiladi.

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

```
function calculateSum(a) {
  let sum = 0;
  for (const value of a) {
    sum += value;
  }
  return sum;
}
```
Ushbu algoritm `a` massiv elementlarining yig'indisini qaytaradi. Massiv uzunligini `n` deb belgilab oladigan bo'lsak, `n` oshib borgani sari algoritm hisoblanishiga ketadigan vaqt - massivning har bir elementini `sum` o'zgaruvchisiga qo'shish kerakligi sababli, u ham birdek oshib boradi. Shuning uchun, algoritm hisoblanishiga ketadigan vaqt `O(n)`. Talab qilinadigan maydon esa faqat `sum` o'zgaruvchisi e'lon qilinganligi sababli `O(1)`.

---

**O(log(n))** - algoritmga kiruvchi qiymatlar o'sib borishi bilan algoritm hisoblanishiga ketadigan vaqt yoki maydon logarifmik ravishda o'sadi.

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

```
function powersOf2(n) {
  if (n < 1) {
    return 0;
  } else if (n === 1) {
    console.log(1);
    return 1;
  } else {
    let prev = powersOf2(Math.floor(n / 2));
    let curr = prev * 2;
    console.log(curr);
    return curr;
  }
}
```
Berilgan funksiya `powersOf2` berilgan `n` sonigacha bo‘lgan 2 ning darajalarini hisoblab chiqadi va chop etadi. Rekursiv ravishda `n` ni yarmiga bo'lish va har bir qadamda 2 ning oldingi darajasini 2 ga ko'paytirish orqali funktsiya `n` ning berilgan qiymatiga qadar 2 ning darajasini hosil qiladi va chop etadi. Masalan: `n = 4` bo'lganida funksiya quyidagicha ishlaydi:
```
powersOf2(4)
  -> powersOf2(2)
    -> powersOf2(1)
      -> chop etish va 1 ni qaytarish
    -> chop etish va 2 ni qaytarish
  -> chop etish va 4 ni qaytarish
```
`n = 4 => n = 2^2` bo'lganida, funksiya 2 marta,
`n = 8 => n = 2^3` bo'lganida, funksiya 3 marta,
`n = 16 => n = 2^4` bo'lganida, funksiya 4 marta chaqirilyapti. Har 2 ning darajalarida funksiya 1ta ko'p chaqiriladi. Tenglikni ikkala tarafini logarifmlab yuborsak, kutgan natijamizga erishamiz:
`n = 4 => log(n) = log(2^2) => log(n) = 2`
Demak, algoritm hisoblanishiga ketadigan vaqt `O(log(n))` ekan. Algoritm hisoblanishiga ketadigan maydon ham funksiya har chaqirilganida avvalgi funksiya qaytargan qiymatni saqlab turishiga joy olganligi sababli `O(log(n))`.

> Algoritmga kiruvchi elementlar soni har safar algoritm ishga tushganida ikki baravar kamayadigan bo'lsa, bu algoritm hisoblanishiga ketadigan vaqt `O(log(n))` bo'lishi mumkin.

---

**O(2^n)** - algoritmga kiruvchi qiymatlar o'sib borishi bilan algoritm hisoblanishiga ketadigan vaqt yoki maydon eksponensial ravishda ortib boradi.

![O(2^n)](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/fgqtddig3eakf27ntuu3.png)

```
function fibonacci(n) {
  if (n <= 0) return 0;
  else if (n === 1) return 1;
  return fibonacci(n - 1) + fibonacci(n - 2);
}
```
Berilgan 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, ...`
`n = 4` bo'lganida funksiya quyidagicha ishlaydi:
```
                             fibonacci(4)
                             /          \
                      fibonacci(3)   fibonacci(2)
                     /  \                     /  \
          fibonacci(2)  fibonacci(1) fibonacci(1) fibonacci(0)
             / \
   fibonacci(1) fibonacci(0)
```
`n = 1` bo'lganida, funksiya 1 marta,
`n = 2` bo'lganida, funksiya 3 marta,
`n = 3` bo'lganida, funksiya 5 marta,
`n = 4` bo'lganida, funksiya 9 marta, 
`n = 5` bo'lganida, funksiya 15 marta,
`n = 6` bo'lganida, funksiya 25 marta chaqirilyapti.
Funksiya chaqiruvlari eksponensial o'sib bormoqda. U deyarlik `O((1.6)^n)` ga yaqin. `1.6` sonini taqriban `2` ga teng deb olib, algoritm hisoblanishiga ketadigan vaqtni `O(2^n)` deb olishimiz mumkin.


![Big O Chart](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/htsnw32gy3736iy23l5z.png)

---

## Big O qoidalari
**O'zgarmaslarni tushirib qoldirish**
`O(n + n) = O(2*n)` - quyidagicha vaqt talab qiluvchi algoritm aslida `O(n)`. Bu yerdagi 2 soni o'zgarmas, ya'ni algoritmga kiruvchi qiymat ortib boragni sari u o'zgarmaydi. Shuning uchun uni bemalol tushirib qoldirish mumkin. 

**Dominant bo'lmaganlarini tushirib qoldirish**
`O(n^2 + n ^2) = O(2 * n^2)` - bundan 2 ni, ya'ni bitta `n^2` ni tushirib qoldirishimiz mumkin (o'zgarmaslarni tushirib qoldirish qoidasiga ko'ra). 
`O(n^2 + n)` - bu ifodadachi? Avvalgi ifodada bemalol bitta `n^2` ni tushirib qoldirgan bo'lsak, bunisida `n` ni ham tushirib qoldirishimiz mumkin. Chunki, u algoritmga kiruvchi qiymat oshib borgani sari `n^2` chalik oshmaydi, uning o'zgarishi deyarli sezilarsiz.

---

## Ko'p qismli algoritmlar
Algoritm bir nechta qismli bo'lishi mumkin. Masalan, quyidagi algoritm 2 o'zgaruvchini oladi (`a` va `b` massivlarini) va ular ustida ishlaydi:

```
function printElements(a, b) {
  for (const aValue of a) {
    console.log(aValue);
  }
  for (const bValue of b) {
    console.log(bValue);
  }
}
```

Ushbu algoritmning hisoblanishiga ketadigan vaqtni aytishga shoshilmang. Birinchi for sikli `a` massiv uzunligi - `A` bo'yicha, ikkinchi `for` sikli `b` massiv uzunligi - `B` bo'yicha vaqt sarflaydi. Avval `a` massiviga, keyin `b` massiviga murojaat qilinmoqda. Shuning uchun, bu yerda algoritm hisoblash vaqtlari qo'shiladi: `O(A + B)`.

```
function printElements(a, b) {
  for (const aValue of a) {
    for (const bValue of b) {
      console.log(aValue, ' , ', bValue);
    }
  }
}
```

Ushbu algoritmda esa hisoblash vaqtlari ko'paytiriladi: `O(A*B)`. Buning sababi, har bir `a` massivi elementi uchun butun `b` massiv elementlariga murojaat qilinmoqda.

## Xulosa:
Xulosa qilib aytganda, **Big O** algoritmlarning samaradorligini tahlil qilish uchun qimmatli vositadir. U algoritmning vaqt yoki maydon talablarini kiruvchi qiymatlar bilan qanday o'lchashni ifodalashning standartlashtirilgan usulini taqdim etadi. Algoritmning **Big O** murakkabligini tushunib, biz uning ishlash xususiyatlarini baholashimiz va algoritmlarni tanlash yoki optimallashtirishda asosli qarorlar qabul qilishimiz mumkin.