3.1-bob: Big-O notatsiyasi (vaqt va xotira murakkabligi)

3-QISM — Algoritm va ma'lumotlar tuzilmasi · 1-mavzu

1. Kirish va motivatsiya

2-QISMda JavaScript'ni o'rgandik — kodni ishlatishni. Endi 3-QISMda kodni samarali yozishni o'rganamiz. Bu — havaskor va professional dasturchini ajratadigan, intervyularning markaziy mavzusi.

Bir muammoni yechishning ko'p yo'li bor — lekin ularning ba'zilari million marta tezroq. Ikkita kod bir xil natija beradi, lekin biri 1 sekundda, ikkinchisi 3 soatda ishlaydi. Big-O notatsiyasi — algoritm qanchalik tez (yoki sekin) ishlashini, ma'lumot o'sganda qanday "kengayishini" o'lchaydigan til.

O'xshatish: siz 10 ta kishini ismi bo'yicha topishingiz kerak. Agar har birini birma-bir so'rasangiz — 10 odam uchun 10 savol, 1000 odam uchun 1000 savol (o'sib boradi). Agar alifbo bo'yicha tartiblangan ro'yxat bo'lsa va o'rtadan qidirsangiz — 1000 odam uchun atigi ~10 savol! Big-O aynan shu "o'sish tezligini" tasvirlaydi.

Nega bu muhim?

• Kichik ma'lumotda farq sezilmaydi, lekin 1 million yozuvda yomon algoritm dasturni muzlatadi (0.5: sahifa qotadi).
• Intervyularda doim so'raladi: "Bu yechimning murakkabligi qancha?"
• 0.1-bobdagi CPU/xotira tushunchasiga tayanadi: Big-O — "CPU necha amal bajaradi" va "necha RAM kerak" degani.
• Butun 3-QISM (data structure tanlovi, saralash, qidiruv) shu o'lchovga asoslanadi.

2. Nazariya — chuqur tushuntirish

2.1. Big-O nima?

Big-O — algoritmning eng yomon holatdagi ishlash vaqtini (yoki xotirasini) kirish hajmiga (n) nisbatan qanday o'sishini tasvirlaydi. Muhim: u aniq vaqtni (sekund) o'lchamaydi — balki o'sish shaklini o'lchaydi.

Nega aniq vaqt emas? Aniq vaqt kompyuterga bog'liq (tez/sekin protsessor — 0.1). Big-O esa algoritmning o'zini baholaydi: "ma'lumot 2 barobar oshsa, ish necha barobar oshadi?". Bu — universal o'lchov.

n — kirish hajmi (massivdagi elementlar soni, matn uzunligi, foydalanuvchilar soni).

2.2. Big-O qanday hisoblanadi: ikki qoida

Qoida 1 — Konstantalarni tashlab yuboring. Big-O o'sish shaklini o'lchaydi, aniq sonni emas:

  5n       O(n)      (5 — konstanta, tashlanadi)
  n/2      O(n)
  3n + 10  O(n)      (kichik qismlar ahamiyatsiz)

Qoida 2 — Eng katta hadni oling (dominant term). n katta bo'lganda eng tez o'suvchi qism hukmron:

  n² + n + 100   O(n²)   (n² eng tez o'sadi; n va 100 ahamiyatsiz)
  n + log n      O(n)

Nega shunday? n = 1,000,000 bo'lsa: n² = trillion, n = million. Million trilion oldida "nol"ga teng. Shuning uchun faqat eng katta had muhim.

2.3. Asosiy Big-O darajalari (sekindan tezgacha)

  TEZLIK         Big-O        Nom              n=1000 da taxminan
  ───────────────────────────────────────────────────────────
  eng yaxshi     O(1)         konstanta        1 amal
       ▲         O(log n)     logarifmik       ~10 amal
       │         O(n)         chiziqli         1 000 amal
       │         O(n log n)   linearitmik      ~10 000 amal
       │         O(n²)        kvadratik        1 000 000 amal
       │         O(2ⁿ)        eksponensial     ulkan (amalda imkonsiz)
  eng yomon      O(n!)        faktorial        astronomik

Endi har birini ko'ramiz.

2.4. O(1) — konstanta vaqt

Kirish hajmidan mustaqil — doim bir xil vaqt:

function birinchi(arr) {
  return arr[0];   // massiv 10 ta yoki 10 million bo'lsin — bitta amal
}

Misollar: massiv indeks bo'yicha murojaat 2.7-bob, obyekt xususiyatiga murojaat 2.8-bob, push/pop 2.7-bob, Map/Set get/has 2.9-bob. Eng yaxshi.

2.5. O(n) — chiziqli vaqt

Har element bilan bir marta ishlash; ma'lumot 2x oshsa, vaqt 2x oshadi:

function yigindi(arr) {
  let s = 0;
  for (const x of arr) s += x;   // har element bo'yicha bir marta (2.2)
  return s;
}

Misollar: for/forEach 2.2-bob, map/filter/reduce 2.7-bob, includes/indexOf/find 2.7-bob. Yaxshi va keng tarqalgan.

2.6. O(n²) — kvadratik vaqt

Ichma-ich tsikl — har element uchun yana barcha elementlar:

function juftliklar(arr) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < arr.length; j++) {   // tsikl ICHIDA tsikl  n × n = n²
      console.log(arr[i], arr[j]);
    }
  }
}

n = 1000 1,000,000 amal. Ehtiyot bo'ling — katta ma'lumotda sekin. Ko'pincha yaxshilash mumkin (Set/Map bilan — 2.9). Ichma-ich tsiklni qanday sanash haqida — 2.11.

2.7. O(log n) — logarifmik vaqt

Har qadamda muammoni yarmiga bo'lish (ajoyib tez):

// Binary search — tartiblangan massivda (3.10-bobda chuqur)
function binaryQidir(arr, qidirilgan) {
  let chap = 0, ong = arr.length - 1;
  while (chap <= ong) {
    const orta = Math.floor((chap + ong) / 2);   // har qadamda yarmini tashla
    if (arr[orta] === qidirilgan) return orta;
    if (arr[orta] < qidirilgan) chap = orta + 1;
    else ong = orta - 1;
  }
  return -1;
}

n = 1,000,000 atigi ~20 amal! Har qadam ma'lumotni yarmiga kamaytiradi. Misol: binary search 3.10-bob, balanslangan daraxt 3.6-bob.

2.8. O(n log n) — saralash darajasi

Eng yaxshi saralash algoritmlarining (merge sort, quick sort — 3.9) tezligi:

const tartiblangan = arr.sort((a, b) => a - b);   // O(n log n) (2.7)

nga yaqin, lekin biroz sekinroq. Samarali saralash uchun "eng yaxshi" daraja.

2.9. Space complexity — xotira murakkabligi

Big-O faqat vaqt emas, xotirani ham o'lchaydi (0.1: RAM): algoritm qancha qo'shimcha xotira ishlatadi?

// O(1) xotira — qo'shimcha xotira o'smaydi
function yigindi(arr) {
  let s = 0;              // bitta o'zgaruvchi (n ga bog'liq emas)
  for (const x of arr) s += x;
  return s;
}

// O(n) xotira — kirish hajmiga mutanosib yangi massiv
function ikkilantir(arr) {
  return arr.map(x => x * 2);   // n ta elementli YANGI massiv (2.7)
}

Vaqt vs xotira savdosi (trade-off): ba'zan tezlikni xotira evaziga sotib olamiz (0.1: caching). Masalan O(n²) qidiruvni O(n) ga tushirish uchun O(n) xotirali Set ishlatamiz 2.9-bob. Bu — muhim qaror.

2.10. Best, average, worst case

Bir algoritmning uch holati bor:

• Best case — eng qulay kirish (masalan qidirilgan element birinchi).
• Average case — odatiy holat.
• Worst case — eng yomon (Big-O odatda shuni oladi — kafolat uchun).

  Linear search:  best O(1) (birinchi), worst O(n) (oxirgi/yo'q)
  Big-O odatda WORST case'ni beradi — "eng yomonda ham shundan yomon emas".

2.11. Tsiklni tahlil qilish — qo'shish va ko'paytirish

Kodning murakkabligini topishning eng amaliy yo'li — tsikllarni sanash. Ikki oddiy qoida bor:

• Ketma-ket (yonma-yon) tsikllar — qo'shiladi. Avval bir tsikl, keyin alohida ikkinchisi: n + n = 2n O(n) (konstanta tashlanadi — 2.2).
• Ichma-ich (biri ichida biri) tsikllar — ko'paytiriladi. Tashqi tsikl n marta, ichkisi har safar n marta: n × n = n² O(n²) 2.6-bob.

// Ketma-ket  O(n) + O(n) = O(n)
for (const x of arr) jamla(x);     // n marta
for (const x of arr) chiqar(x);    // yana n marta (qo'shiladi)

// Ichma-ich  O(n) × O(n) = O(n²)
for (const x of arr)               // n marta...
  for (const y of arr)             // ...har biri uchun yana n marta (ko'paytiriladi)
    juftla(x, y);

Diqqat — ichki tsikl chegarasiga qarang. Agar ichki tsikl n emas, doimiy sondan (masalan har doim 3 marta) aylansa — bu O(n), O(n²) emas: n × 3 = 3n O(n). Murakkablikni belgilovchi narsa — ichki tsikl n ga bog'liqmi, yo'qmi.

Demak: kodga qarab, "necha marta ichma-ich tsikl n ga bog'liq aylanadi?" deb sanang — har bir bog'liq qatlam n ni bir martaga ko'paytiradi.

2.12. Amortized murakkablik — "o'rtacha qiymat ko'p amal bo'yicha"

Ba'zi operatsiyalar ko'pincha tez, lekin vaqti-vaqti bilan sekin. Amortized murakkablik — bunday operatsiyaning ko'p chaqiruv bo'yicha o'rtacha narxini beradi (worst case bilan adashtirmang — 2.10).

Klassik misol — massivga push. Odatda O(1), lekin massiv to'lib qolganda dvigatel uni kattaroq joyga ko'chiradi (barcha elementlarni nusxalaydi — o'sha bitta chaqiruv O(n)). Lekin bu kamdan-kam bo'lgani uchun, ko'chirish narxi keyingi ko'p pushlarga taqsimlanadi:

  Bitta push: odatda O(1), goho O(n) (ko'chirish)
  n ta push:  jami ~2n amal  har push O(1) AMORTIZED

Shuning uchun jadvallarda push amortized O(1) deb yoziladi (3-bo'lim). Xuddi shu g'oya Hash Table'ning o'rtacha O(1) si (2.9, 3.5) va dinamik massivlar ostida yotadi: "ba'zan qimmat, lekin o'rtacha arzon".

3. Asosiy ma'lumotnoma — murakkablik jadvali

Ma'lumotlar tuzilmalari operatsiyalari (o'rtacha holat — bigocheatsheet asosida; 3.3–3.6 da chuqur):

* oxiriga push — amortized O(1) 2.12-bob; ** bosh/ma'lum joyda. (Worst case'da Hash Table O(n).)

Saralash 3.9-bob:

4. Batafsil kod namunalari

Misol 1 — Murakkablikni aniqlash

// O(1) — kirishdan mustaqil (2.4)
function oxirgi(arr) { return arr[arr.length - 1]; }

// O(n) — bitta tsikl (2.5)
function maksimum(arr) {
  let max = arr[0];
  for (const x of arr) if (x > max) max = x;   // n marta
  return max;
}

// O(n²) — ichma-ich tsikl (2.6)
function takrorBormi(arr) {
  for (let i = 0; i < arr.length; i++)
    for (let j = i + 1; j < arr.length; j++)   // tsikl ichida tsikl
      if (arr[i] === arr[j]) return true;
  return false;
}

Misol 2 — O(n²) ni O(n) ga yaxshilash (vaqt vs xotira — 2.9)

//  O(n²) — har element uchun qolganini tekshirish (2.6)
function takrorBormiSekin(arr) {
  for (let i = 0; i < arr.length; i++)
    for (let j = i + 1; j < arr.length; j++)
      if (arr[i] === arr[j]) return true;
  return false;
}

//  O(n) — Set bilan (O(n) xotira evaziga — 2.9, 2.9-Set)
function takrorBormiTez(arr) {
  const korilgan = new Set();
  for (const x of arr) {
    if (korilgan.has(x)) return true;   // O(1) qidiruv (2.9)
    korilgan.add(x);
  }
  return false;
}
// 1 million elementda: sekin versiya soatlar, tez versiya bir lahza

Misol 3 — O(log n) binary search vs O(n) linear search

const n = 1_000_000;
const arr = Array.from({ length: n }, (_, i) => i);   // [0,1,2,...] tartiblangan

// O(n) — eng yomonda 1 million amal (2.5)
function linear(arr, x) {
  for (let i = 0; i < arr.length; i++) if (arr[i] === x) return i;
  return -1;
}

// O(log n) — eng yomonda ~20 amal (2.7)
function binary(arr, x) {
  let l = 0, r = arr.length - 1;
  while (l <= r) {
    const m = (l + r) >> 1;          // o'rta (yarmiga bo'lish)
    if (arr[m] === x) return m;
    arr[m] < x ? (l = m + 1) : (r = m - 1);
  }
  return -1;
}
// binary 50,000 marta tezroq! (lekin massiv TARTIBLANGAN bo'lishi shart)

Misol 4 — Murakkablikni o'lchash (amalda)

function olcha(fn, n) {
  const arr = Array.from({ length: n }, (_, i) => i);
  console.time(`n=${n}`);
  fn(arr, -1);                       // eng yomon holat (topilmaydi)
  console.timeEnd(`n=${n}`);
}
// linear: n oshganda vaqt mutanosib oshadi (O(n))
// binary: n 10x oshganda vaqt deyarli o'zgarmaydi (O(log n))
[1000, 10000, 100000].forEach(n => olcha(linear, n));

5. To'g'ri va noto'g'ri holatlar

1) Ichma-ich tsikl (Set/Map o'rniga)

//  O(n²) — katta ma'lumotda sekin (2.6)
const umumiy = arr1.filter(x => arr2.includes(x));   // includes har safar O(n)

//  O(n) — Set bilan (2.9)
const set2 = new Set(arr2);
const umumiy = arr1.filter(x => set2.has(x));         // has — O(1)

2) Massivda tez-tez qidiruv (Set o'rniga)

//  tsiklda includes — O(n²) (2.6)
for (const x of katta) if (royxat.includes(x)) {...}

//  Set — O(n) (2.9)
const set = new Set(royxat);
for (const x of katta) if (set.has(x)) {...}

3) Erta optimizatsiya (premature optimization)

 10 elementli massivni "tezlashtirish" uchun murakkab kod yozish
 Avval ishlaydigan, o'qishli kod; sekinlik isbotlansa — optimallashtiring

Nega: kichik nda O(n²) ham bir lahza. Optimizatsiya — kerak bo'lganda (o'lchab — Misol 4).

4) Tartiblanmagan massivda binary search

//  binary search faqat TARTIBLANGAN massivda ishlaydi (2.7)
binary([5, 2, 8, 1], 8);   // noto'g'ri natija!

//  avval tartibla (yoki linear)
binary([1, 2, 5, 8], 8);

6. Keng tarqalgan xatolar va yechimlari

Xato 1 — Dastur katta ma'lumotda muzlaydi

Sababi: O(n²) yoki yomonroq algoritm 2.6-bob. Yechimi: ichma-ich tsiklni Set/Map bilan O(n) ga tushiring (Misol 2); murakkablikni hisoblang.

Xato 2 — RangeError: Maximum call stack (rekursiyada)

Sababi: chuqur/cheksiz rekursiya — har chaqiruv stack xotirasi (0.1, 2.4). Yechimi: base case 3.11-bob; kerak bo'lsa tsikl bilan.

Xato 3 — JavaScript heap out of memory

Sababi: O(n) yoki yomon xotira — juda katta massiv/struktura (0.1, 2.9). Yechimi: stream bilan ishlang 5.4-bob; xotira murakkabligini kamaytiring.

Xato 4 — "Mening kompyuterimda tez, serverda sekin"

Sababi: kichik test ma'lumoti — O(n²) sezilmaydi; production'da katta ma'lumot. Yechimi: katta nda test qiling; murakkablikni nazariy hisoblang.

Xato 5 — Hash Table O(1) deb ko'r-ko'rona ishonish

Sababi: Hash Table o'rtacha O(1), lekin worst case O(n) (kolliziyalar — 3.5). Yechimi: odatda O(1), lekin chegaraviy holatlarni biling.

7. Integratsiya — bu mavzu stack'ning qayerida uchraydi

• Data structures (3.3–3.8): har birining tanlovi murakkablikka asoslanadi (3-bo'lim jadvali).
• Saralash/qidiruv (3.9, 3.10): Big-O — bu algoritmlarni taqqoslash o'lchovi.
• Array/Set/Map (2.7, 2.9): metodlarning murakkabligini bilish — to'g'ri tanlov.
• DB indekslar (6.3, 6.9): indeks — O(n) qidiruvni O(log n) ga tushiradi.
• Performance (0.5, 11.11): sekin kod — ko'pincha yomon Big-O.
• System Design 15.7-bob: masshtab (scalability) — Big-O bilan o'lchanadi.
• Caching (0.1, 5.21): vaqt vs xotira savdosi 2.9-bob.

8. Eng yaxshi amaliyotlar (best practices)

• Murakkablikni o'ylab kod yozing — ayniqsa ichma-ich tsikl ko'rsangiz, "O(n²) kerakmi?" deb so'rang.
• Tez qidiruv uchun Set/Map (O(1)) — includes/indexOf tsiklda emas 2.9-bob.
• Erta optimizatsiya qilmang — avval ishlaydigan kod; sekinlik isbotlansa optimallashtiring (5-bo'lim).
• Katta nda test qiling — kichik test yomon algoritmni yashiradi (6-bo'lim).
• Vaqt vs xotira savdosini ongli qiling — tezlikni xotira evaziga 2.9-bob.
• Eng katta hadga e'tibor — konstantalar emas 2.2-bob.
• Worst case'ni biling — kafolat uchun 2.10-bob.
• Tartiblangan ma'lumotda binary search (O(log n)) — chiziqli o'rniga 2.7-bob.

9. Amaliy loyiha: "Algoritm Tezligi O'lchagichi"

Big-O ni ko'z bilan ko'rish loyihasi — nazariyani amaliyotga bog'laydi.

Maqsad

Turli murakkablikdagi funksiyalarni yozib, ularning vaqtini turli nda o'lchab, Big-O o'sish shaklini amalda tasdiqlash.

Talablar (requirements)

1. O'lchov funksiyasi: berilgan funksiya va n uchun vaqtni console.time bilan o'lchaydi (Misol 4, 0.5).
2. O(1) misol: massivning oxirgi elementini qaytaruvchi funksiya.
3. O(n) misol: yig'indi yoki maksimum (Misol 1).
4. O(n²) misol: takrorni ichma-ich tsikl bilan topish (Misol 2 sekin versiya).
5. O(n) yaxshilangan: xuddi shu takrorni Set bilan (Misol 2 tez versiya) — ikkalasini solishtiring.
6. O(log n) misol: binary search (Misol 3) — linear bilan solishtiring.
7. Jadval: har funksiyani n = 1000, 10000, 100000, 1000000 da o'lchab, vaqtlarni jadval qilib chiqar.
8. Tahlil: har funksiya uchun "n 10x oshganda vaqt necha barobar oshdi?" ni yozing va Big-O bilan solishtiring.
9. (Bonus) Xotira murakkabligini ham muhokama qiling (qaysi funksiya qo'shimcha xotira ishlatadi — 2.9).

Maslahatlar (hint)

• Array.from({length: n}, (_, i) => i) — test massivi.
• console.time("nom") ... console.timeEnd("nom") 0.5-bob.
• O(n): n 10x vaqt ~10x. O(n²): n 10x vaqt ~100x. O(log n): n 10x vaqt deyarli o'zgarmaydi.
• Binary search uchun massiv tartiblangan bo'lsin (4-holat).
• Juda katta n (10⁸) da O(n²) ni ishlatmang — muzlaydi (ataylab kichikroq).

"Tayyor" mezonlari (acceptance criteria)

• O(1), O(n), O(n²), O(log n) funksiyalari yozilgan.
• Takror topish O(n²) va O(n) versiyalarda; tez versiya aniq tezroq.
• Binary va linear search solishtirilgan (binary ancha tez).
• Vaqtlar jadvali turli n uchun chiqarilgan.
• Har funksiya uchun "10x necha barobar" tahlili Big-O ga mos.
• Tartiblanmagan massivda binary ishlatilmagan.

Yechim kodi ataylab berilmagan — bu loyihani o'zingiz yozib ko'ring.

10. Xulosa va keyingi bobga ko'prik

Bu bobda algoritm samaradorligini o'lchovchi — Big-O notatsiyasini o'rgandik:

• Big-O — algoritmning worst case ishlash vaqti/xotirasi kirish hajmi n ga nisbatan qanday o'sishini tasvirlaydi (aniq sekund emas — shakl).
• Hisoblash: konstantalarni tashlang, eng katta hadni oling 2.2-bob.
• Darajalar: O(1) (konstanta) < O(log n) (yarmiga bo'lish) < O(n) (chiziqli) < O(n log n) (saralash) < O(n²) (ichma-ich tsikl) < O(2ⁿ) < O(n!).
• Space complexity — qo'shimcha xotira; vaqt vs xotira savdosi (Set bilan O(n²)O(n)).
• Best/average/worst case; data structure va algoritm tanlovi shu o'lchovga asoslanadi.

Keyingi bob — 3.2-bob: Massiv va String algoritmlari. Big-O o'lchovini bildik; endi uni amalda qo'llaymiz. Massiv va string — eng ko'p uchraydigan ma'lumot; ular ustidagi klassik algoritmlar (ikki ko'rsatkich, sliding window, prefiks yig'indi) intervyularning va kundalik ishning asosi.

Foydalanilgan rasmiy/ishonchli manbalar

• bigocheatsheet.com — Big-O Algorithm Complexity Cheat Sheet (data structure va sorting murakkabliklari)
• MDN Web Docs — Array/Map/Set metodlari murakkabligi
• Universal CS nazariyasi — asymptotic notation, time/space complexity