Big-O notatsiyasi — vaqt va xotira murakkabligi, misollar bilan (3.1-bob)

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

2.13. Senior Architect: Asimptotik notatsiyalar oilasi va Hardware Cache Locality siri

Katta tizimlarni loyihalashda algoritmlarni faqat matematik formulalar bilan emas, kompyuter apparat ta'minoti (CPU/RAM arxitekturasi) bilan birgalikda baholash talab etiladi.

1. Asimptotik notatsiyalar oilasi: $O$, $\Omega$, $\Theta$

Ko'p dasturchilar har qanday tahlilni "Big-O" deb atashga o'rganib qolgan. Lekin nazariy informatika (Computer Science) uchta aniq belgilashni ajratadi:

1. Big-O ($O$ — Yuqori chegara / Upper Bound):
   • Algoritm eng yomon holatda ham ushbu funksiyadan sekin ishlamaydi ($f(n) \le c \cdot g(n)$).
   • Bu dasturchining "Bundan battar bo'lmaydi" degan kafolatidir.
2. Big-Omega ($\Omega$ — Quyi chegara / Lower Bound):
   • Algoritm eng qulay holatda eng kamida qancha vaqt olishini bildiradi ($f(n) \ge c \cdot g(n)$).
   • Masalan, massivdan qidirishda $\Omega(1)$ — element birinchi urinishdayoq topilsa.
3. Big-Theta ($\Theta$ — Aniq chegara / Tight Bound):
   • Agar algoritmning yuqori va quyi chegarasi bir xil funksiya bilan cheklansa ($c_1 \cdot g(n) \le f(n) \le c_2 \cdot g(n)$), bu $\Theta$ deb ataladi.
   • Masalan: $n$ ta elementli massiv yig'indisini hisoblash har doim $\Theta(n)$ dir — u $n$ dan kam ham, ko'p ham bo'la olmaydi. Intervyularda dasturchilar Big-O deganlarida ko'pincha aynan $\Theta$ ni nazarda tutishadi.

2. Yordamchi xotira (Auxiliary Space) vs Jami xotira (Total Space)

Xotira murakkabligini hisoblashda eng ko'p adashiladigan nozik nuqta:

• Total Space (Jami xotira): Kiruvchi argumentlar va algoritm yaratgan barcha xotira yig'indisi.
• Auxiliary Space (Yordamchi xotira): Algoritm ishlashi uchun qo'shimcha talab qilingan yangi xotira.

function yigindiHisobla(kattaMassiv) {
  // kattaMassiv hajmi: n
  let sum = 0; // Faqat 1 ta o'zgaruvchi
  for (let i = 0; i < kattaMassiv.length; i++) {
    sum += kattaMassiv[i];
  }
  return sum;
}

Ushbu funksiyada:

• Jami xotira: $O(n)$ (chunki massiv xotirada $n$ joy egallab turibdi).
• Yordamchi xotira (Auxiliary Space): $O(1)$ (chunki algoritm yangi massiv ochmadi, faqat bitta sum o'zgaruvchisi bilan ishladi). Algoritm samaradorligi doim Auxiliary Space bo'yicha baholanadi!

3. Hardware Reality (Mechanical Sympathy): Nega nazariy $O(n)$ amalda farq qiladi?

Nega $100,000$ ta elementli Massiv (Array) bo'ylab yurish xuddi shuncha elementli Bog'langan Ro'yxat (Linked List) bo'ylab yurishdan 10 barobardan 50 barobargacha tezroq bajariladi, holbuki ikkalasining ham nazariy murakkabligi $O(n)$?

Sababi — Zamonaviy CPU L1/L2/L3 Kesh Liniyalari (Cache Lines — 64 bayt):

• Massiv (Array): Xotirada yonma-yon yaxlit blok bo'lib joylashadi. Protsessor birinchi elementni o'qiganida, apparat ta'minoti (Hardware Spatial Prefetcher) keyingi 64 baytlik qo'shni elementlarni ham avtomatik tarzda eng yuqori tezlikdagi L1 keshga yuklab oladi. Natijada keyingi qadamlar xotirani kutmaydi (Cache Hit — 1ns).
• Linked List: Tugunlar (Node) operativ xotiraning (RAM) turli chekkalariga sochilib ketgan. Har safar node.next qilinganda, protsessor xotiradan yangi manzilni qidiradi. Keshda u yo'q bo'lgani uchun Cache Miss yuz beradi va protsessor sekin RAM'dan ma'lumot kelishini yuzlab takt davomida bo'sh kutib turishga majbur bo'ladi (~100-200 CPU cycles).

Xulosa: Katta hajmdagi ma'lumotlar bilan ishlashda ketma-ket xotira (Contiguous Memory) doimo tarqoq ko'rsatkichli tuzilmalardan ustun turadi!

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 tartiblang (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 chiqaring.
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