Oldingi maqolada biz Θ (theta) qiymatlarini ya'ni best case va worst caseni topişni körib çiqdik. Best case yana lower bound ham deyiladi, Worst case - upper bound.

Algoritm complexity'ni aniqlaşda köpinça upper bound'ni topişga e'tibor beriladi. Ana şu upper bound - Big O, uni topiş - Big O ni topiş deyiladi. Linear search'da körib çiqqanimiz lower bound - 1, upper bound N bölsa, Big O = N böladi. Yozilişi - O(n).

Nima uçun upper bound'ga e'tibor beriladi? Sababi lower bound qiymati upper bound içida böladi baribir. Masalan, Insertion sort uçun lower bound O(n), upper bound O(n²), bunda O(n²) öz içiga O(n) ni ham olgan böladi.

Savol, ba'zi algoritmlarda bir neça sikllar, amallar işlatilgan bö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 boşqa funksiyaga boğlanmagan bölsa, "constant" bölib O(1) ga teng böladi.

Sikllarda qadamga qaraladi. Birinçi sikl 0 dan N gaça, demak linear, ya'ni O(n). Ikkinçi, ikkitalik siklda qadamlar soni O(n²) teng, ya'ni quadratic.

Ketma-ket amallar qöşib yoziladi: f(1 + n + k²)

Bundan time complexity ni topiş uçun constant'lar tuşirib qoldiriladi. Demak yuqoridagi funksiya uçun time complexity O(n + k²).

Uşbu jadvalda time complexity'larni best to worse tartibida körib çiqamiz.

Algoritm murakkabligi jadvali

 

Algoritm murakkabligi diagramma körinişida