Big O termini haqida

Oldingi maqolada biz Θ (theta) qiymatlarini ya’ni best case va worst caseni topishni ko’rib chiqdik. Best case yana lower bound ham deyiladi, Worst case – upper bound.

Algoritm complexity’ni aniqlashda ko’pincha upper bound’ni topishga e’tibor beriladi. Ana shu upper bound – Big O, uni topish – Big O ni topish deyiladi. Linear search’da ko’rib chiqqanimiz lower bound – 1, upper bound N bo’lsa, Big O = N bo’ladi. Yozilishi – O(n).

Nima uchun upper bound’ga e’tibor beriladi? Sababi lower bound qiymati upper bound ichida bo’ladi baribir. Masalan, Insertion sort uchun lower bound O(n), upper bound O(n2), bunda O(n2) o’z ichiga O(n) ni ham olgan bo’ladi.

Savol, ba’zi algoritmlarda bir necha sikllar, amallar ishlatilgan bo’ladi, u holda time complexity qanday qilib topiladi?

Misol:

function test(arr) {
  const a = b + c
  const N = arr.length
  const K = 123 // Some value

  for (let i = 0; i < N; i++) {
    ...
  }
  ...
  for (let i = 0; i < K; i++) {
    for (let j = 0; j < K; i++) {
      ...
    }
  }
}

Oddiy amallar, matematik amallar, agar ular rekursiya, sikl, yoki boshqa funksiyaga bog’lanmagan bo’lsa, «constant» bo’lib O(1) ga teng bo’ladi.

Sikllarda qadamga qaraladi. Birinchi sikl 0 dan N gacha, demak linear, ya’ni O(n). Ikkinchi, ikkitalik siklda qadamlar soni O(n2) teng, ya’ni quadratic.

Ketma-ket amallar qo’shib yoziladi: f(1 + n + k2)

Bundan time complexity ni topish uchun constant’lar tushirib qoldiriladi. Demak yuqoridagi funksiya uchun time complexity O(n + k2).

Ushbu jadvalda time complexity’larni best to worse tartibida ko’rib chiqamiz.

Algoritm murakkabligi jadvali
Algoritm murakkabligi jadvali

 

Algoritm murakkabligi diagramma ko’rinishida