"Big O" haqida gaplashamiz

#algorithms #javascript #programming #tutorial

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.

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.

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.

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.

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 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.