Big-O notatsiyasi: ma'lumot ko'payganda algoritm qanchalik sekinlashadi

Qisqacha: Big-O — ma'lumot ko'payganda dastur bajaradigan ish qanday o'sishini ko'rsatadigan qisqa yozuv. U soniyalarni emas, o'sish shaklini aytadi: O(n) — ma'lumot ikki baravar ko'paysa, ish ham ikki baravar ko'payadi; O(n²) — to'rt baravar; O(1) — ish o'zgarmaydi. Hisoblashda ikki qoida bor: o'zgarmas ko'paytuvchi tashlanadi (2n → n) va faqat eng tez o'sadigan qism qoladi (n² + n → n²).

Bu darsda

• Algoritm bajaradigan ishni qadamlar bilan sanay olasiz — soniyasiz.
• Ma'lumot ikki baravar ko'payganda vaqt qanday o'zgarishini o'lchab, Big-O bilan bog'lay olasiz.
• O(1), O(n) va O(n²) yozuvlarini o'qiy olasiz va ularni kodda taniysiz.
• Big-O'ning ikki qoidasini qo'llay olasiz: o'zgarmas sonlarni tashlash va dominant hadni qoldirish.

Oldin bilishingiz kerak: Algoritm nima, Chegaraviy holatlar va brute force, Map, Performansni o'lchash va benchmarking, Birinchi avtomatik test.

1. Nega bu kerak?

14-qism boshlandi. Bu qismda algoritmlar bilan ishlaymiz: qidirish, saralash, daraxt va graflar. Lekin avval bitta savolga javob kerak: "Qaysi yechim yaxshiroq?" Bunga javob berish uchun yechimlarni bir xil "o'lchov tili" bilan solishtirish kerak. Bugun shu tilni o'rganamiz.

«Bahor» oshxonasida voqea bo'ldi. Stajyor Sardor buyurtmalar ichidan takroriy buyurtmani topadigan funksiya yozdi: mijoz tugmani ikki marta bosib yuborsa, bitta buyurtma ikki marta tushadi. Sardor funksiyani 20 ta sinov buyurtmasida tekshirdi — bir zumda ishladi. Jasur aka uni bir yillik arxivga — 50 000 buyurtmaga qo'ydi. Dastur bir necha soniya o'ylab qoldi.

Jasur aka so'radi: "Keyingi yil buyurtmalar 100 000 ta bo'ladi. Shunda qancha kutamiz?" Sardor javob bera olmadi. "Bilmayman, kompyuterga bog'liq" — bu javob emas. Javob shunday bo'lishi kerak: "Buyurtmalar ikki baravar ko'paysa, kutish to'rt baravar ko'payadi." Buni hisoblashni o'rganamiz.

Kursda bu darsga bir nechta va'da bor:

• Set darsida includes va has tezligini o'lchab, "buni O(n) va O(1) deb belgilashadi" degan edik.
• Benchmarking darsida includes → Set.has almashtirish 50 000 elementda 850 baravar yutuq berdi. "Ish hajmining o'sishini o'lchaydigan til — Big-O" degan edik.
• ReDoS darsida har harf vaqtni ikki baravar oshirdi — "eksponensial" o'sish.

Bugun bu gaplarning hammasi bitta tizimga tushadi.

2. Qadamlarni sanaymiz

2.1 Menyudan taom qidirish

Soniyalar kompyuterga bog'liq: Jasur akaning noutbuki bir tezlikda ishlaydi, Sardorning telefoni — boshqa tezlikda. Lekin bitta narsa hamma joyda bir xil — algoritm bajaradigan qadamlar soni. Shuning uchun avval soniyani emas, qadamni sanaymiz.

Birinchi masala: menyuda taom bormi? Eng sodda yo'l — taomlarni boshidan bittalab ko'rib chiqish. Bu chiziqli qidiruv (linear search) — ro'yxatni boshidan oxirigacha bittalab tekshirish. Qanday ishlashini qadamma-qadam ko'ring. Ko'rsatkich i — hozir qaysi katakka qarayotganimizni bildiruvchi indeks. U har safar bitta katakka suriladi, ko'rib bo'lingan taomlar xiralashadi:

"kabob" oltinchi o'rinda edi — 6 ta solishtirish kerak bo'ldi. Endi funksiyaga hisoblagich qo'shamiz va menyu kattalashganda qadamlar qanday o'zgarishini ko'ramiz. steps — "qadamlar" — har solishtirishda bittaga oshadi:

function findDish(menu, name) {
  let steps = 0; // nechta solishtirish qildik
  for (let i = 0; i < menu.length; i++) {
    steps++;
    if (menu[i] === name) return steps;
  }
  return steps; // topilmadi — hammasini ko'rdik
}

for (const n of [10, 100, 1000]) {
  const menu = Array.from({ length: n }, (_, i) => `taom-${i + 1}`);
  console.log(`${n} ta taom:`, findDish(menu, "pitsa"), "qadam");
}

Konsolda:

10 ta taom: 10 qadam
100 ta taom: 100 qadam
1000 ta taom: 1000 qadam

Array.from({ length: n }, …) — n ta elementli massiv yasaydi (Array.from). Menyuda "pitsa" yo'q, shuning uchun funksiya hamma taomni ko'rib chiqdi. Natija oddiy: menyudagi taomlar soni qancha bo'lsa, qadamlar ham shuncha.

2.2 n — ma'lumot hajmi

Algoritmlarda ma'lumot hajmini bitta harf bilan belgilash odat bo'lgan — n. Menyu qidiruvida n — taomlar soni. Buyurtmalar bilan ishlasak — buyurtmalar soni. Matn bilan — harflar soni.

Endi qadamlarni n orqali aytish mumkin: "chiziqli qidiruv eng ko'pi bilan n qadam qiladi". Bu gap 10 ta taomli kafe uchun ham, 1000 ta taomli restoran uchun ham to'g'ri.

"Eng ko'pi bilan" so'ziga e'tibor bering. Taom ro'yxat boshida bo'lsa, bitta qadam yetadi. Oxirida yoki umuman yo'q bo'lsa — n qadam. Algoritmni baholaganda odatda eng yomon holat (worst case) olinadi — eng ko'p ish talab qiladigan kirish. Sababi oddiy: "omadimiz kelsa tez" degan va'da mijozga yetmaydi. Eng yaxshi va o'rtacha holatlarni Xotira murakkabligi va eng yomon holat darsida chuqur ko'ramiz.

2.3 Hamma juftlarni solishtirish

Endi Sardorning masalasi: buyurtmalar ichida takror bormi? Sodda yechim — brute force (Chegaraviy holatlar va brute force): har buyurtmani qolgan hamma buyurtmalar bilan solishtirish. Ichma-ich ikki sikl kerak. Tashqi sikl i bitta buyurtmani tanlaydi, ichki sikl j uni o'zidan keyingilar bilan solishtiradi:

5 ta buyurtma — 10 ta solishtirish. Nega j i + 1 dan boshlanadi? 101 ni 102 bilan solishtirsak, 102 ni 101 bilan qayta solishtirish shart emas. Buyurtmani o'zi bilan solishtirish ham kerak emas. Endi kattaroq n uchun sanaymiz:

function countPairChecks(orders) {
  let checks = 0;
  for (let i = 0; i < orders.length; i++) {
    for (let j = i + 1; j < orders.length; j++) {
      checks++; // orders[i] va orders[j] solishtirildi
    }
  }
  return checks;
}

for (const n of [5, 10, 100, 1000]) {
  const orders = Array.from({ length: n }, (_, i) => i + 1);
  console.log(`${n} ta buyurtma:`, countPairChecks(orders), "juft");
}

Konsolda:

5 ta buyurtma: 10 juft
10 ta buyurtma: 45 juft
100 ta buyurtma: 4950 juft
1000 ta buyurtma: 499500 juft

Jadvalga solamiz va ikki masalani yonma-yon qo'yamiz:

Qidiruvda n 10 baravar oshsa, qadamlar ham 10 baravar oshadi. Juftlarda esa 100 baravar! Sababi: n ta buyurtmaning har biri taxminan n ta boshqasi bilan uchrashadi. Bu taxminan n × n ning yarmi.

Tekshirib ko'ring: Arxivda 50 000 ta buyurtma bor. Sardorning funksiyasi (takror topilmasa) taxminan nechta solishtirish qiladi?

3. O'lchaymiz: n ikki baravar oshsa

3.1 Qanday o'lchadik

Qadam sanash — nazariya. Endi haqiqiy kompyuterda tekshiramiz. O'lchash usuli — benchmarking darsidagidek. Eslatib o'tamiz: isitish — kodni avval bir necha marta bekorga ishlatib, JavaScript dvigateliga uni tezlashtirishga vaqt berish. Mediana — natijalarni saralaganda o'rtada turgani: bitta tasodifiy sekin o'lchov uni buzmaydi. Har o'lcham alohida jarayonda 5 marta ishga tushirildi.

// olchov.mjs — node olchov.mjs 1000000
const n = Number(process.argv[2]);
const menu = Array.from({ length: n }, (_, i) => `taom-${i}`);
let sink = 0; // natija ishlatilsin (o'lik kod bo'lmasin)
const time = olcha(() => {
  sink += findDish(menu, "yo'q taom"); // eng yomon holat
}, { isitish: 5, marta: 11 });
console.log(n, time.toFixed(2), "ms", sink !== 0);

olcha — o'sha darsda yozgan yordamchimiz. Bu yerda u 5 marta isitadi, 11 marta o'lchaydi va medianani qaytaradi. Taom menyuda yo'q — har safar eng yomon holat. Aniq millisekundlar sizning kompyuteringizda boshqacha chiqadi — shuning uchun hamma joyda "taxminan" deymiz.

3.2 Natija: ikki baravar va to'rt baravar

Chiziqli qidiruv (bitta qidiruv, taom yo'q):

Juftlarni solishtirish (takror yo'q):

Raqamlarni o'zaro emas, qatorma-qator solishtiring. Qidiruvda har qatorda vaqt taxminan ikki baravar oshdi (shovqin bor: 1,5 dan 2,4 gacha). Juftlarda — har safar taxminan to'rt baravar: 1,3 → 5,6 → 21 → 89. Ikki masalani bitta rasmda ko'ramiz. Har chiziq "vaqt birinchi o'lchamga nisbatan necha baravar oshdi" ni ko'rsatadi:

Nimaga qarang: qidiruv chizig'i deyarli to'g'ri ko'tariladi — n necha baravar oshsa, vaqt ham taxminan shuncha. Juftlar chizig'i esa tepaga "uchib" ketadi: n 8 baravar oshdi, vaqt — 69 baravar (nazariyada 64). Qadam sanash buni oldindan aytgan edi.

3.3 Jasur akaning savoliga javob

Endi Sardor javob bera oladi. 50 000 buyurtma bir necha soniya oldi. 100 000 — ikki baravar ko'p, demak kutish to'rt baravar uzoq. 200 000 bo'lsa — o'n olti baravar. Kompyuter nomini bilmasdan, faqat algoritm tuzilishidan shu xulosaga keldik.

Bu shunday ishlaydi: aniq soniyalar kompyuterga bog'liq, nisbat esa algoritmga bog'liq. Big-O aynan nisbat haqida gapiradi.

3.4 Uchinchi xil: o'sishning umuman yo'qligi

Narxni taom nomi bo'yicha olish uchun Map ishlatsak-chi?

const prices = new Map([
  ["osh", 35000],
  ["lag'mon", 28000],
  ["manti", 30000],
  ["ko'k choy", 5000],
]);

console.log(prices.get("manti")); // 30000

Map qiymatni ro'yxatni ko'rib chiqmasdan topadi — kalitdan "manzil" hisoblaydi va to'g'ri o'sha joyga qaraydi (Set darsidagi raqamli ilgaklar). O'lchadik: 1 000 000 marta get qildik, Map ichidagi taomlar sonini 1 000 dan 1 000 000 gacha oshirdik:

Ma'lumot 1000 baravar oshdi — vaqt deyarli joyida qoldi (14–21 ms oralig'idagi farq — shovqin). Bitta get taxminan 15–20 nanosekund — menyu qanchalik katta bo'lmasin. Massivda indeks bilan olish ham shunday: menu[3] 7 ta taomli ro'yxatda ham, million taomlida ham bitta qadam.

4. Big-O belgisi

4.1 Uchta o'sish turi

Endi ko'rganlarimizga nom beramiz. Big-O notatsiyasi (Big-O notation) — ma'lumot hajmi n o'sganda algoritm ishi qanday o'sishini ko'rsatadigan yozuv. "Notatsiya" — "yozish usuli", "belgilash". O'qilishi: "bi-o" yoki o'zbekcha "katta O". O(n) — "o en" deb o'qiladi.

Ularning nomlari ham bor: O(1) — o'zgarmas vaqt (constant time), O(n) — chiziqli vaqt (linear time), O(n²) — kvadratik vaqt (quadratic time). n² — "n kvadrat", ya'ni n × n.

"O" harfi inglizcha "order" — "tartib, daraja" so'zidan. Matematiklar uni "o'sish tartibi" ma'nosida ishlatadi. Bizga bitta gap yetadi: O(...) ichidagi ifoda ish qanday o'sishini aytadi, qancha ekanini emas.

Bu oshxonaga o'xshaydi. Tayyor manti qozonidan bitta likopchaga solish — mehmonlar soniga bog'liq emas, bitta ish (O(1)). Har mehmonga choy quyish — mehmonlar qancha bo'lsa, shuncha ish (O(n)). Har mehmonni boshqa har bir mehmon bilan tanishtirish — mehmonlar ikki baravar ko'paysa, tanishtirish to'rt baravar ko'payadi (O(n²)).

4.2 "n katta bo'lganda" degani

Big-O ma'lumot juda katta bo'lgandagi o'sishni ko'rsatadi. Buni asimptotik o'sish (asymptotic growth) deyishadi: n cheksiz kattalashgan sari nima bo'lishiga qaraymiz. Kichik n da boshqa narsalar ham muhim bo'lishi mumkin — lekin Big-O ular haqida gapirmaydi.

Taksi bilan o'xshatish. Toshkentda taksi narxi: chiqish 5 000 so'm, keyin har kilometr 2 000 so'm. Bir kilometrlik yo'lda chiqish narxi katta ulush — 7 000 ning 5 000 i. Yuz kilometrlik yo'lda esa 205 000 so'mning atigi 5 000 i — sezilmaydi. Uzoq yo'lda narxni kilometrlar belgilaydi. Big-O ham "uzoq yo'l" haqida: n katta bo'lganda ishni nima belgilaydi?

Tekshirib ko'ring: Algoritm 1 000 ta buyurtmani 2 soniyada ishladi va u O(n). 3 000 ta buyurtma uchun taxminan qancha vaqt kerak? O(n²) bo'lsa-chi?

5. Birinchi qoida: o'zgarmas sonlar tashlanadi

5.1 Ikki sikl — 2n qadam

Jasur aka menyudagi eng arzon va eng qimmat narx orasidagi farqni bilmoqchi. Sardor ikkita alohida sikl yozdi: biri eng kichigini, ikkinchisi eng kattasini topadi.

function findPriceRange(prices) {
  let steps = 0;
  let min = Infinity;
  for (const price of prices) {
    steps++;
    if (price < min) min = price;
  }
  let max = -Infinity;
  for (const price of prices) {
    steps++;
    if (price > max) max = price;
  }
  return { range: max - min, steps };
}

console.log(findPriceRange([35000, 28000, 30000, 5000]));
// { range: 30000, steps: 8 }

Infinity — "cheksizlik": har qanday son undan kichik, shuning uchun birinchi narx darhol min ga tushadi (Ma'lumot turlari). 4 ta narx — 8 qadam. n ta narx — 2n qadam. Demak, O(2n)?

Yo'q — O(n). Big-O'ning birinchi qoidasi: o'zgarmas ko'paytuvchi tashlanadi. 2n, 3n, n ÷ 2, n + 100 — hammasi O(n).

5.2 Nega tashlash mumkin?

Uchta sabab bor.

Birinchi — nisbat o'zgarmaydi. n ikki baravar oshsa, 2n ham ikki baravar oshadi: 2 × 1000 = 2000, 2 × 2000 = 4000. O'sish shakli — chiziqli. findPriceRange ni o'lchadik: 250 ming, 500 ming, 1, 2 va 4 million narxda vaqt ≈ 4,6 → 10,8 → 23 → 44 → 86 ms bo'ldi. Har qadamda — taxminan ikki baravar, xuddi findDish kabi.

Ikkinchi — "qadam" o'zi aniq emas. Bitta solishtirish protsessorda bir necha amal bo'lishi mumkin; for...of va oddiy for turli tezlikda ishlaydi (benchmarking darsidagi jadval). Demak, 2n ning "2" si kompyuter, dvigatel va yozish uslubiga qarab baribir o'zgaradi. Uni hisoblash ma'nosiz.

Uchinchi — O(n²) bilan solishtirganda ahamiyatsiz. n = 100 000 da 2n = 200 000, n² esa 10 000 000 000. O(n) ning "2" si bu farq oldida hech narsa emas.

Maslahat: "Ikki sikl o'rniga bitta sikl yozsam, Big-O yaxshilanadimi?" — Yo'q, ikkalasi ham O(n). Kod biroz tezlashishi mumkin, lekin o'sish shakli o'sha. Katta yutuq faqat o'sish turini o'zgartirganda keladi: O(n²) → O(n).

6. Ikkinchi qoida: dominant had qoladi

6.1 Ikki qism — qaysi biri muhim?

Sardor takror qidirishdan oldin buyurtmalarni bir marta ko'rib chiqadi — bo'sh buyurtma yo'qligini tekshiradi (n qadam). Keyin hamma juftlarni solishtiradi (taxminan n² ÷ 2 qadam). Jami: n² ÷ 2 + n. Ikkinchi qism — bitta sikl — qanchalik muhim?

for (const n of [10, 100, 1000, 10000]) {
  const pairs = (n * (n - 1)) / 2; // juftlar
  const total = pairs + n; // + bitta tekshiruv sikli
  const share = ((n / total) * 100).toFixed(2);
  console.log(`n=${n}: jami ${total}, sikl ulushi ${share}%`);
}

Konsolda:

n=10: jami 55, sikl ulushi 18.18%
n=100: jami 5050, sikl ulushi 1.98%
n=1000: jami 500500, sikl ulushi 0.20%
n=10000: jami 50005000, sikl ulushi 0.02%

10 ta buyurtmada tekshiruv sikli ishning beshdan biriga yaqin. 10 000 tada — ming ulushdan ham kam. n o'sgan sari n² hamma narsani "yutib" yuboradi.

6.2 Qoida

Ifodaning har bir qo'shiluvchi qismi had deyiladi: n² ÷ 2 + n da ikkita had bor. Dominant had (dominant term) — n o'sganda eng tez o'sadigan had. Big-O'ning ikkinchi qoidasi: faqat dominant had qoladi, qolganlari tashlanadi. Keyin birinchi qoida bilan o'zgarmas son ham tashlanadi:

n² ÷ 2 + n → n² ÷ 2 → O(n²)

Bir nechta misol:

Uchinchi qatorga qarang: 500 qadam — ko'p, lekin u n ga bog'liq emas. Menyu 10 ta bo'lsa ham, million bo'lsa ham — 500. Demak, O(1). "O'zgarmas vaqt" — "bitta qadam" degani emas, "n ga bog'liq emas" degani.

Endi o'zingiz qo'llang. Ifoda: 4n² + 10n + 7. n = 1000 bo'lsin. Birinchi had 4n² = [:4000000], ikkinchisi 10n = [:10000], uchinchisi 7. Birinchi had qolgan ikkalasidan 400 baravar katta — u dominant. Demak, Big-O — O(n²).

Tekshirib ko'ring: To'rtinchi qatorda n² ÷ 10 bor — n² ning o'ndan biri. n = 5 da n² ÷ 10 = 2,5, n esa 5. Kichik n da n katta-ku. Nega baribir O(n²)?

7. Big-O nimani aytmaydi

7.1 Soniyalarni aytmaydi

O(n) algoritm O(n²) dan har doim tezmi? Katta n da — ha. Kichik n da — har doim emas. Masalan, bitta algoritm aslida 100n qadam qiladi (O(n)), boshqasi n² qadam (O(n²)). n = 10 da birinchisi 1 000 qadam, ikkinchisi 100 — kvadratik tezroq! Ular n = 100 da tenglashadi, keyin chiziqli algoritm doim oldinda.

Shuning uchun ikkita amaliy qoida:

• Ma'lumot kichik va kichik qolsa (menyuda 30 ta taom) — eng tushunarli kodni yozing.
• Ma'lumot o'sishi mumkin bo'lsa (buyurtmalar arxivi, foydalanuvchilar) — Big-O'ni o'ylang.

7.2 Va'dani bajaramiz: includes va Set.has

Endi benchmarking darsidagi jadvalni tushuntira olamiz. U yerda n ta so'rovning har biri n ta bron ichidan qidirilgan edi:

includes — chiziqli qidiruv, O(n). U n marta chaqirildi, jami n × n = O(n²). Shuning uchun n 10 baravar oshganda vaqt taxminan 100 baravar oshdi (0,85 → 81). Set.has — O(1), u ham n marta chaqirildi, jami O(n). Bu yerda n 10 baravar oshganda vaqt taxminan 5 baravar oshdi (kichik vaqtlarda shovqin ko'p). 850 baravar farqning siri — "mikro-hiyla" emas, o'sish turi.

7.3 Boshqa o'sish turlari ham bor

O(1), O(n), O(n²) — faqat boshlanishi. ReDoS darsidagi naqsh har harfda vaqtni ikki baravar oshirgan edi — bu O(2ⁿ), eksponensial o'sish. Saralangan menyuda esa qidiruvni O(n) dan ancha tez qilish mumkin — "menyuni ikkiga bo'lib" qidirish. Bularni keyingi darsda ko'ramiz.

8. Ko'p uchraydigan xatolar

8.1 Big-O'ni soniya deb o'ylash

"Bu algoritm O(n), demak 1 ms ishlaydi" — noto'g'ri. O(n) vaqtni emas, vaqt qanday o'zgarishini aytadi. To'g'ri gap: "n ikki baravar oshsa, vaqt taxminan ikki baravar oshadi."

8.2 Kod qatorlarini sanash

"Funksiya 3 qator — demak O(1)" — noto'g'ri. menu.includes(name) bitta qator, lekin ichida butun massivni ko'radi — O(n). Qatorlarni emas, n ga bog'liq takrorlanishni qidiring: sikllar va ichida sikl yashiradigan metodlar. Ularni JS o'rnatilgan amallarining narxi darsida birma-bir ko'ramiz.

8.3 O(2n) yoki O(n² + n) deb yozish

Xato emas, lekin shunday yozilmaydi. Ikki qoidani qo'llang va eng sodda shaklni yozing: O(n), O(n²). Intervyuda "O(2n)" desangiz, "soddalashtiring" deb so'rashadi.

8.4 Faqat "omadli" holatni ko'rish

"Taom odatda ro'yxat boshida bo'ladi, demak qidiruv tez" — xavfli fikr. Big-O odatda eng yomon holat uchun aytiladi. Menyuda yo'q taomni qidirish — kundalik holat, va u har doim n qadam.

9. Mashqlar

1-mashq (oson): Jadvalni to'ldiring

Chiziqli qidiruv (eng yomon holat) va hamma juftlarni solishtirish uchun qadamlar sonini yozing: n = 20 va n = 40. Ishora: juftlar soni — n × (n − 1) ÷ 2.

2-mashq (o'rta): Soddalashtiring

Har ifoda uchun Big-O'ni yozing va qaysi qoidani qo'llaganingizni ayting: 7n + 3, n ÷ 2, 2n² + 1000n, 1 000 000, n + n + n.

3-mashq (qiyin): Testda isbotlang

kurs/mashqlar/14/01-big-o/juftlar.test.mjs faylini yarating. Unda countPairChecks(n) funksiyasi bo'lsin: ichma-ich ikki sikl bilan n ta buyurtma uchun juftlar sonini sanasin (formula bilan emas). Uchta test yozing (node:test va assert):

1. 0 va 1 ta buyurtma — 0 juft (chegaraviy holatlar).
2. 5 ta buyurtma — 10 juft.
3. n = 1000 dan n = 2000 ga o'tganda juftlar soni 3,9 dan 4,1 baravargacha oshadi — kvadratik o'sishning isboti.

Ishora: uchinchi testda assert.ok(shart, xabar) — shart false bo'lsa, xabar bilan yiqiladi.

// kurs/mashqlar/14/01-big-o/juftlar.test.mjs
import { test } from "node:test";
import assert from "node:assert/strict";

function countPairChecks(n) {
  let checks = 0;
  for (let i = 0; i < n; i++) {
    for (let j = i + 1; j < n; j++) {
      checks++;
    }
  }
  return checks;
}

test("0 va 1 ta buyurtma — solishtirish yo'q", () => {
  assert.equal(countPairChecks(0), 0);
  assert.equal(countPairChecks(1), 0);
});

test("5 ta buyurtma — 10 juft", () => {
  assert.equal(countPairChecks(5), 10);
});

test("n ikki baravar — juftlar taxminan 4 baravar", () => {
  const ratio = countPairChecks(2000) / countPairChecks(1000);
  assert.ok(ratio > 3.9 && ratio < 4.1, `nisbat: ${ratio}`);
});

✔ 0 va 1 ta buyurtma — solishtirish yo'q (0.7802ms)
✔ 5 ta buyurtma — 10 juft (0.1422ms)
✔ n ikki baravar — juftlar taxminan 4 baravar (3.3158ms)
ℹ tests 3
ℹ suites 0
ℹ pass 3
ℹ fail 0
ℹ cancelled 0
ℹ skipped 0
ℹ todo 0
ℹ duration_ms 87.6699

4-mashq: Amaliy tajriba — murakkablik jadvali

Endi 14-qism davomida har algoritm murakkabligini bitta jadvalga yozib borasiz. Intervyuga tayyorlanishda shu jadval eng foydali varaq bo'ladi. Bugun kurs/mashqlar/14/MURAKKABLIK.md faylini yarating va bugungi uchta yechimni yozing: menyudan qidirish, takroriy buyurtmani topish (juftlar bilan) va Map dan narx olish. Ustunlar: masala, yechim, vaqt (Big-O), bir gaplik "nega".

# Murakkablik jadvali (14-qism)

| Masala | Yechim | Vaqt | Nega |
|---|---|---|---|
| Menyudan taom qidirish | chiziqli qidiruv | O(n) | eng yomon holatda hamma taomni ko'radi |
| Takroriy buyurtma | hamma juftlar | O(n²) | ichma-ich ikki sikl, ~n²/2 juft |
| Taom narxi | Map.get | O(1) | kalitdan to'g'ri joyga boradi |

git add 14/MURAKKABLIK.md 14/01-big-o
git commit -m "14/01: Big-O — murakkablik jadvali va juftlar testi"

10. Real ishda

• Kod ko'rib chiqish (code review). Tajribali dasturchi siklning ichida includes, find yoki filter ko'rsa, darhol so'raydi: "Bu ro'yxat qancha katta bo'lishi mumkin?" Bu — Big-O bilan o'ylash.
• Ma'lumot o'sishi. Ko'p "sekin sayt" muammolari birinchi kuni ko'rinmaydi. 100 foydalanuvchida hammasi tez, 100 000 da — qotadi. O(n²) kod odatda aynan shunday "kech portlaydi".
• Intervyu. Deyarli har texnik intervyuda yechimdan keyin savol bor: "Bu yechimning vaqt murakkabligi qanday?" Javob Big-O bilan beriladi va "nega" tushuntiriladi.
• Hujjatlar. Kutubxona va til hujjatlarida amallar narxi ko'pincha Big-O bilan yoziladi — masalan, ma'lumotlar bazasi indeksi qidiruvni O(n) dan ancha tezroq qiladi, buni Indeks nima darsida ko'ramiz.

Xulosa

• Algoritmni soniya bilan emas, qadamlar bilan baholaymiz: soniyalar kompyuterga bog'liq, qadamlar — yo'q.
• n — ma'lumot hajmi. Big-O n ikki baravar oshganda ish qanday o'sishini aytadi: O(1) — o'zgarmaydi, O(n) — ikki baravar, O(n²) — to'rt baravar.
• O'lchov buni tasdiqladi: qidiruv har safar ≈ 2 baravar, juftlar ≈ 4 baravar sekinlashdi; Map.get ma'lumot 1000 baravar o'sganda ham joyida qoldi.
• Birinchi qoida: o'zgarmas ko'paytuvchi tashlanadi (2n → O(n)). Ikkinchi qoida: dominant had qoladi (n² + n → O(n²)).
• Big-O katta n haqida; kichik ma'lumotda tushunarli kod muhimroq.

Keyingi dars: Asosiy murakkablik sinflari — O(1) dan O(n!) gacha: har birining tipik kodi, "menyuni ikkiga bo'lib" qidirish (O(log n)) va qaysi n da qaysi algoritm hali ishlaydi.

Manbalar

• Thomas H. Cormen va boshq., "Introduction to Algorithms", 4-nashr, MIT Press, 2022 — 3-bob (asimptotik belgilar).
• MDN: Map — developer.mozilla.org (amallar "o'rtacha subchiziqli vaqtda" bajarilishi talabi — ECMAScript spetsifikatsiyasidan).
• ECMAScript 2025 spetsifikatsiyasi, "Map Objects" bo'limi — tc39.es/ecma262