Big-O murakkablik sinflari: O(1) dan O(n!) gacha — tipik kod va amaliy chegara

Qisqacha: Algoritmlarning ko'pi yettita sinfdan biriga tushadi. Tezdan sekinga: O(1) — o'zgarmas, O(log n) — har qadamda yarmini tashlaydi, O(n) — hammasini bir marta ko'radi, O(n log n) — yaxshi saralash, O(n²) — hamma juftlar, O(2ⁿ) — hamma to'plamlar, O(n!) — hamma tartiblar. Birinchi to'rttasi million elementda ham ishlaydi. O(n²) — o'n minglab elementgacha, O(2ⁿ) — taxminan 25 tagacha, O(n!) — 10–11 tagacha.

Bu darsda

• Yettita asosiy murakkablik sinfini tezlik tartibida ayta olasiz va har biriga «Bahor»dan misol keltira olasiz.
• log₂ n nima ekanini "menyuni ikkiga bo'lish" orqali tushuntira olasiz va ikkiga bo'lib qidirishni qadamma-qadam kuzatasiz.
• Kod qaysi sinfga tushishini uning tuzilishidan taniysiz.
• Ma'lumot hajmiga qarab qaysi sinf hali ishlashini taxminlay olasiz.

Oldin bilishingiz kerak: Big-O notatsiyasi, Rekursiya asoslari, sort va taqqoslash funksiyasi, Set.

1. Nega bu kerak?

O'tgan darsda uchta o'sish turini ko'rdik: O(1), O(n) va O(n²). Ular bir-biridan juda farq qildi. Lekin «Bahor»da Jasur akaning masalalari ko'payib ketdi va har biri o'zgacha:

1. Kassa daftaridagi buyurtmalar raqam bo'yicha tartiblangan. 15-raqamli buyurtmani qanday tez topish mumkin?
2. Kun oxirida hamma buyurtmalarni summasi bo'yicha saralash kerak.
3. Mehmon Dilshod akaning byudjeti 100 000 so'm. Menyudagi qaysi taomlar to'plami unga sig'adi?
4. Kuryer 10 ta manzilga borishi kerak. Qaysi tartibda yursa, yo'l eng qisqa?

To'rtala masala to'rt xil sinfga tushadi. Ba'zilari million ma'lumotda ham bir zumda yechiladi. Ba'zilari esa 20–30 ta elementdayoq "o'lib qoladi". Bugun shu yettita sinfni birma-bir ko'ramiz: kodi, o'lchovi va chegarasi bilan.

Bu oshxonadagi pichoq, qozon va tandirga o'xshaydi: har asbobning o'z ishi va o'z chegarasi bor. Tandirda 50 ta non yopsa bo'ladi, 5 000 tasini — yo'q. Qaysi asbob qayergacha yetishini bilgan oshpaz ishni to'g'ri rejalashtiradi.

2. O(1) — o'zgarmas vaqt

Eng tez sinf. Ish ma'lumot hajmiga bog'liq emas. Bu sinfga kiradi:

• massivdan indeks bilan olish: menu[3], orders.at(-1);
• Map va Set da qidirish: prices.get("osh"), bron.has(15);
• oddiy hisob: price * qty, total + 5000.

const orders = [12000, 35000, 28000, 30000];
const prices = new Map([["osh", 35000], ["manti", 30000]]);

console.log(orders[0]); // 12000
console.log(orders.at(-1)); // 30000
console.log(prices.get("osh") * 2); // 70000

Massivda 4 ta yoki 4 million element bo'lsin — orders[0] bitta qadam. Buni o'tgan darsda o'lchadik: Map dan million marta o'qish 1 000 va 1 000 000 elementda ham taxminan bir xil vaqt oldi.

3. O(log n) — har qadamda yarmini tashlash

3.1 Menyu kitobi o'yini

Jasur aka Sardorga o'yin taklif qildi. "Menyu kitobida 1000 ta taom bor, hammasi alifbo tartibida. Men bittasini o'yladim. Sen sahifa ochasan, men esa faqat 'oldinroq' yoki 'keyinroq' deyman. Nechta urinishda topasan?"

Sardor birinchi sahifadan boshlasa — 1000 ta urinish ham ketishi mumkin. Lekin u aqlliroq yo'l tanladi: kitobni o'rtasidan ochdi. "Keyinroq" — demak, birinchi yarmi kerak emas, 500 ta taom qoldi. Yana o'rtasidan ochdi — 250 qoldi. Keyin 125, 63, 32, 16, 8, 4, 2, 1. Hammasi bo'lib 10 ta urinish!

Har urinish qolgan taomlarni yarmiga qisqartiradi. Savol bitta: 1000 ni necha marta ikkiga bo'lsa, bitta qoladi? Bu savolning javobi — ikki asosli logarifm, qisqacha log₂ n. U shunchaki "n ni necha marta ikkiga bo'lish mumkin" degani. Maktabdagi logarifm formulalarini eslamasangiz ham qo'rqmang — bu kursda bizga faqat shu ma'no kerak. Sanab ko'ramiz:

function countHalvings(n) {
  let steps = 0;
  while (n > 1) {
    n = Math.ceil(n / 2); // yarmi qoladi (toq bo'lsa — kattarog'i)
    steps++;
  }
  return steps;
}

for (const n of [8, 1000, 1_000_000, 1_000_000_000]) {
  console.log(`${n}: ${countHalvings(n)} marta`);
}

Konsolda:

8: 3 marta
1000: 10 marta
1000000: 20 marta
1000000000: 30 marta

Math.ceil — sonni yuqoriga yaxlitlaydi: 125 ÷ 2 = 62,5 → 63 (Math obyekti). 1_000_000 — million; _ faqat o'qish qulayligi uchun, son o'zgarmaydi.

Natijaga qarang: menyu ming baravar kattalashdi (1000 dan million), urinishlar esa atigi 10 taga ko'paydi. Milliardta taomda ham — 30 ta urinish. Bu — logarifmning sehri. n ikki baravar oshsa, log₂ n atigi bittaga oshadi: 1000 da 10, 2000 da 11.

Maslahat: Matematikada logarifmning asosi boshqacha bo'lishi ham mumkin (10, 3). Big-O'da asos yozilmaydi — O(log n). Sababi: turli asosli logarifmlar bir-biridan o'zgarmas ko'paytuvchiga farq qiladi, u esa birinchi qoida bo'yicha tashlanadi. Bizga "ikkiga bo'lish" ma'nosi yetadi.

3.2 Ikkiga bo'lib qidirish

Bu o'yinning kodi — ikkiga bo'lib qidirish (binary search). U faqat saralangan ro'yxatda ishlaydi: o'rtadagi elementga qaraydi va izlangan qiymat qaysi yarmida ekanini aniqlaydi. Uchta ko'rsatkich bor: left — chap chet, right — o'ng chet, mid — o'rtasi. Oyna (rangli qism) — hali "shubhali" qism:

15 ta raqamdan to'rttasiga qaradik. Chiziqli qidiruv 13 ta solishtirish qilgan bo'lardi. Kodning qadamlarini sanaymiz — eng yomon holatda, ya'ni raqam ro'yxatda yo'q bo'lganda:

function binarySearch(sorted, target) {
  let left = 0;
  let right = sorted.length - 1;
  let steps = 0;
  while (left <= right) {
    steps++;
    const mid = Math.floor((left + right) / 2);
    if (sorted[mid] === target) return { index: mid, steps };
    if (sorted[mid] < target) left = mid + 1;
    else right = mid - 1;
  }
  return { index: -1, steps };
}

for (const n of [1000, 1_000_000]) {
  const orders = Array.from({ length: n }, (_, i) => i + 1);
  const result = binarySearch(orders, n + 1); // yo'q raqam
  console.log(`${n} ta buyurtma: ${result.steps} qadam`);
}

Konsolda:

1000 ta buyurtma: 10 qadam
1000000 ta buyurtma: 20 qadam

Menyu o'yinidagi raqamlarning aynan o'zi. Bu algoritmni Binary search asoslari darsida chuqur o'rganamiz: chegaralar, tuzoqlar va variantlar. Hozir bitta xulosa muhim: saralangan ma'lumotda qidirish O(log n).

3.3 O'lchov

Million marta qidirdik — n ni 10 baravardan oshirib:

Ro'yxat ming baravar kattalashdi, vaqt esa taxminan 6 baravar oshdi. Nazariya 2 baravar deydi (10 → 20 qadam). Farq qayerdan? Kichik massiv protsessorning eng tez xotirasiga to'liq sig'adi, katta massivning har qismiga murojaat esa sekinroq. Buni Massiv xotirada darsida ko'ramiz. Lekin baribir: n ming baravar oshdi — vaqt olti baravar. Chiziqli qidiruv ming baravar sekinlashgan bo'lardi.

Tekshirib ko'ring: Toshkentda taxminan 3 million odam yashaydi. Saralangan telefon ro'yxatida ikkiga bo'lib qidirish eng ko'pi bilan nechta qadam qiladi? Ishora: 2²⁰ ≈ 1 million.

4. O(n) — chiziqli vaqt

Har elementni bir marta (yoki o'zgarmas marta) ko'radigan algoritm. Chekning jami, eng arzon taom, menyudan qidirish — hammasi O(n):

function calculateTotal(prices) {
  let total = 0;
  for (const price of prices) {
    total += price; // har narx — bir marta
  }
  return total;
}

console.log(calculateTotal([35000, 28000, 5000])); // 68000

O'lchov: 1 million narx — taxminan 0,8 ms, 10 million — 9,7 ms, 100 million — 140 ms. n o'n baravar — vaqt ham taxminan o'n baravar. Agar javob uchun hamma ma'lumotni ko'rish shart bo'lsa (masalan, jami summa), O(n) dan tez bo'lishi mumkin emas: ko'rmagan narxni qo'sha olmaysiz.

5. O(n log n) — yaxshi saralash

5.1 Saralash nechta solishtirish qiladi?

Kun oxirida buyurtmalarni summa bo'yicha saralaymiz — toSorted bilan. Taqqoslash funksiyasi necha marta chaqirilganini sanaymiz. Sonlar har safar bir xil chiqishi uchun "urug'li" tasodifiy generator ishlatamiz: bir xil boshlang'ich son (urug') — har safar bir xil ketma-ketlik.

function makeRandom(seed) {
  // har chaqiruvda keyingi son; urug' bir xil — ketma-ketlik ham
  return () => (seed = (seed * 16807) % 2147483647);
}

const random = makeRandom(2026);
for (const n of [1000, 2000, 4000, 8000]) {
  const nums = Array.from({ length: n }, random);
  let comparisons = 0;
  nums.toSorted((a, b) => {
    comparisons++;
    return a - b;
  });
  const nLogN = Math.round(n * Math.log2(n));
  console.log(`n=${n}: ${comparisons} ta, n·log₂n ≈ ${nLogN}`);
}

Konsolda:

n=1000: 8616 ta, n·log₂n ≈ 9966
n=2000: 19257 ta, n·log₂n ≈ 21932
n=4000: 42575 ta, n·log₂n ≈ 47863
n=8000: 93077 ta, n·log₂n ≈ 103726

Math.log2(n) — JavaScript'ning tayyor log₂ funksiyasi. Solishtirishlar soni n · log₂ n ga juda yaqin — biroz kamroq ham. n ikki baravar oshganda solishtirishlar ikki baravardan biroz ko'proq oshdi: n ham ikki baravar, log₂ n ham bittaga oshdi.

5.2 Nega n · log n?

Yaxshi saralash algoritmlari ishni "qatlamlarga" bo'ladi. Ro'yxatni ikkiga, har yarmini yana ikkiga bo'lib, yakkama-yakka elementgacha boradi. Bu — log₂ n qatlam (menyu o'yinidagidek). Keyin qatlamma-qatlam qaytib, bo'laklarni tartib bilan birlashtiradi. Har qatlamda hamma n element bir martadan ko'riladi. Jami: log₂ n qatlam × n ish = n · log n. Bu sinf chiziqli-logarifmik (linearithmic) deb ham ataladi.

Bu g'oyani Merge sort darsida kod bilan ko'ramiz. JavaScript'ning sort va toSorted metodi Node 24 (V8 13.6) da TimSort algoritmidan foydalanadi — u ham O(n log n). Eng yangi Chrome'da uning o'rnini yaqin "qarindoshi" PowerSort egallagan, sinfi o'sha. Ikkalasini JS sort ichidan darsida ko'ramiz.

5.3 O'lchov

Har qatorda vaqt ikki baravardan biroz ko'proq oshdi — 2,0 dan 2,3 baravargacha. n · log n aynan shuni kutadi: n ikki baravar, log n esa biroz oshadi. Kvadratik saralash bu yerda har safar to'rt baravar sekinlashgan bo'lardi. 1,6 million sonni saralash — taxminan 0,6 soniya.

Tekshirib ko'ring: Sardor so'radi: "Saralangan ro'yxatda qidirish O(log n) ekan. Unda har qidiruvdan oldin toSorted qilib, keyin ikkiga bo'lib qidirsam, tez bo'ladimi?" Nima deysiz?

6. O(n²) — kvadratik vaqt

O'tgan darsda ko'rdik: hamma juftlarni solishtirish — taxminan n² ÷ 2 qadam, O(n²). Tanish belgisi — ichma-ich ikki sikl, ikkalasi ham n gacha boradi. Takroriy buyurtmalarni qidirish, har mehmonni har mehmon bilan solishtirish, oddiy saralashlar (bubble, selection, insertion) — hammasi shu sinfda.

Juftlarni solishtirishni kattaroq n da ham o'lchadik: 32 000 buyurtma — ≈ 290 ms, 50 000 — ≈ 700 ms. Buyurtmalar 1,56 baravar ko'paydi, vaqt esa 2,4 baravar — bu taxminan 1,56 × 1,56. Kvadratik qoida yana bajarildi.

O(n²) "yomon" degani emas. 1 000 ta elementda bu 500 ming qadam — bir necha millisekund. Muammo n o'n minglab bo'lganda boshlanadi.

7. O(2ⁿ) — eksponensial vaqt

7.1 Hamma to'plamlar

Dilshod aka 40 000 so'm bilan kirdi: "Qaysi taomlarni birga olsam, pulim yetadi?" Har taom uchun ikki yo'l bor: olamiz yoki olmaymiz. Ikki taom — 2 × 2 = 4 xil to'plam. Uch taom — 2 × 2 × 2 = 8. n ta taom — 2 ni n marta ko'paytirish, ya'ni 2ⁿ to'plam.

Sodda yechim hamma to'plamlarni rekursiya bilan ko'rib chiqadi (Rekursiya asoslari). Funksiya har taomda o'zini ikki marta chaqiradi: bir marta "olindi" (take), bir marta "olinmadi" (skip). Daraxtni kuzating: chap shox — taom olindi, o'ng shox — olinmadi. Tugundagi raqam — shu paytgacha yig'ilgan summa, ming so'mda:

3 ta taom — pastki qatorda 8 ta to'plam. Endi taomlar sonini oshirib, to'plamlarni sanaymiz va vaqtni o'lchaymiz.

7.2 Bitta taom — ikki baravar

Bu jadvalning boshqa jadvallardan farqiga qarang: n bittaga oshdi — vaqt ikki baravar. O(n²) da vaqtni to'rt baravar oshirish uchun n ni ikki baravar oshirish kerak edi. Bu yerda esa bitta taom yetadi. 30 ta taomda — milliardtadan ortiq to'plam; 50 tada esa bu kompyuter taxminan to'rt oy hisoblaydi.

ReDoS darsidagi yovuz naqsh ham shunday edi: har harf vaqtni ikki baravar oshirdi. Endi bu o'sishning nomini bilasiz — eksponensial (exponential), O(2ⁿ).

Diqqat: Eksponensial algoritm kichik sinovda doim tez ko'rinadi: 10 ta taom — 1024 to'plam, bir zumda. Haqiqiy menyuda 40 ta taom bo'lsa — trillion. Rekursiv funksiya o'zini ikki marta chaqirayotganini ko'rsangiz, to'xtab o'ylang.

Bunday masalalarning ko'pini tezlashtirish mumkin: keraksiz shoxlarni kesish (Backtracking va kesish) yoki natijalarni eslab qolish (Dinamik dasturlash).

8. O(n!) — faktorial vaqt

8.1 Kuryer yo'li

Kuryer 3 ta manzilga boradi: Chilonzor, Yunusobod, Sergeli. Nechta tartib bor? Birinchi manzilni 3 xil tanlash mumkin, ikkinchisini — qolgan 2 tadan, uchinchisi — oxirgi bitta. Jami 3 × 2 × 1 = 6. Bu ko'paytma faktorial deyiladi va undov belgisi bilan yoziladi: 3! = 6, 4! = 24, 5! = 120.

Hamma tartiblarni sanaydigan funksiya. U har qadamda hali borilmagan manzillardan birini tanlaydi va qolganlari uchun o'zini chaqiradi:

function countRoutes(addresses, visited = new Set()) {
  if (visited.size === addresses.length) return 1; // yo'l tayyor
  let total = 0;
  for (const address of addresses) {
    if (visited.has(address)) continue;
    visited.add(address); // shu manzilga boramiz
    total += countRoutes(addresses, visited);
    visited.delete(address); // qaytamiz, boshqasini sinaymiz
  }
  return total;
}

console.log(countRoutes(["Chilonzor", "Yunusobod", "Sergeli"]));
for (const n of [5, 7, 9]) {
  const list = Array.from({ length: n }, (_, i) => `manzil-${i}`);
  console.log(`${n} ta manzil: ${countRoutes(list)} yo'l`);
}

Konsolda:

6
5 ta manzil: 120 yo'l
7 ta manzil: 5040 yo'l
9 ta manzil: 362880 yo'l

Hamma tartiblarni yasash usulini Backtracking asoslari darsida chuqur o'rganamiz. Hozir faqat sonlarga qarang.

8.2 Eng tez o'sadigan sinf

Manzillar bittaga ko'paydi — vaqt n baravar oshdi: 9 da 10 baravar, 10 da yana 10 baravar, 11 da yana taxminan 12 baravar. Agar manzillar 15 ta bo'lsa, trillionta tartib chiqadi — bu kompyuterda taxminan olti kun. Kuryerlar esa kuniga 30–40 manzilga boradi!

Shuning uchun haqiqiy yetkazish xizmatlari hamma tartibni sinamaydi. Ular "yetarlicha yaxshi" yo'lni tez topadigan usullardan foydalanadi: masalan, har safar eng yaqin manzilga borish (Greedy algoritmlar). Eng qisqa yo'llarni topishni Eng qisqa yo'l darsida ko'ramiz.

9. Hammasi bitta rasmda

Yettita sinfni yonma-yon qo'yamiz. Grafikda n = 1 dan 10 gacha qadamlar soni (hisob). n! juda tez o'sgani uchun grafikka sig'maydi — 10 da u 3,6 million:

Nimaga qarang: n = 10 da ham O(2ⁿ) chizig'i boshqalarni "yerga yotqizib" qo'ydi. n = 4 gacha esa hammasi deyarli bir xil — kichik ma'lumotda farq sezilmaydi. Sinflar tezlik tartibida:

10. Qaysi n da qaysi sinf ishlaydi

Endi eng amaliy savol: algoritm bir soniyada qancha ma'lumotni hal qila oladi? Har sinf uchun o'lchovlarimizdan taxmin qildik (Node 24, noutbuk protsessori):

Bu raqamlar sizning kompyuteringizda boshqacha bo'ladi — ikki-uch baravar farq qilishi mumkin. Lekin tartibi o'zgarmaydi: O(n²) hech qachon million elementni bir soniyada yecha olmaydi, O(2ⁿ) — 50 tani.

Amaliy qoida: masala shartida n ning chegarasini ko'rsangiz, undan qaysi sinf kerakligini taxmin qilasiz.

• n ≤ 10 — hatto n! ham o'tadi.
• n ≤ 25 — 2ⁿ mumkin.
• n ≤ 10 000 — n² bemalol o'tadi (50 000 atrofida — chegara).
• n ≥ 100 000 — n log n yoki undan tezi kerak.

Masala yechish saytlarida (LeetCode, Codeforces) shartdagi chegaralar aynan shu maqsadda yoziladi.

Tekshirib ko'ring: «Bahor» mijozlari bazasida 200 000 kishi. Sardor har mijozni har mijoz bilan solishtirib, takror telefon raqamlarini qidirmoqchi. Bu qancha vaqt oladi? Nima tavsiya qilasiz?

11. Ko'p uchraydigan xatolar

11.1 Saralanmagan ro'yxatda ikkiga bo'lib qidirish

Ikkiga bo'lib qidirish faqat saralangan ma'lumotda ishlaydi. Saralanmagan [30, 5, 35, 28] da u xato javob beradi — xato xabarisiz, jimgina. binarySearch([30, 5, 35, 28], 5) → -1, garchi 5 bor bo'lsa ham. Tuzatish: ma'lumot saralanganiga ishonch hosil qiling yoki chiziqli qidiruv ishlating.

11.2 2ⁿ va n² ni chalkashtirish

Ikkalasida ham "2" bor, lekin ular butunlay boshqa. n² da n — asos, 2 — daraja: 20² = 400. 2ⁿ da 2 — asos, n — daraja: 2²⁰ = 1 048 576. Tuzatish: "n bittaga oshsa nima bo'ladi?" deb so'rang. n² da deyarli o'zgarmaydi, 2ⁿ da ikki baravar.

11.3 Kichik sinovga ishonish

10 ta taom bilan sinalgan eksponensial yoki faktorial kod "tez" ko'rinadi. Tuzatish: sinovda haqiqiy hajmni ham bering yoki kodning sinfini oldindan hisoblang.

11.4 Hamma narsani O(1) qilishga urinish

O(n) ko'p masalada eng yaxshi mumkin bo'lgan natija: jami summani hisoblash uchun hamma narxni ko'rish shart. Tuzatish: "javob uchun hamma ma'lumot kerakmi?" deb so'rang. Kerak bo'lsa — O(n) dan tez bo'lmaydi.

12. Mashqlar

1-mashq (oson): Sinfni aniqlang

Har vaziyat uchun sinfni ayting:

• (a) menyuning birinchi taomini olish;
• (b) chekdagi eng qimmat taomni topish;
• (c) saralangan bron vaqtlari ichidan 19:00 ni ikkiga bo'lib qidirish;
• (d) har ofitsiantni har ofitsiant bilan juft qilib navbatchilik jadvali tuzish;
• (e) 12 ta taomning hamma to'plamini sinash.

2-mashq (o'rta): Ikkiga bo'lishni sanang

Jadvalni qo'lda to'ldiring (kodsiz): ikkiga bo'lib qidirish eng ko'pi bilan nechta qadam qiladi? n = 16, 1 024, 2 048, 1 000 000. Keyin javobingizni darsdagi countHalvings bilan tekshiring. Ishora: 2⁴ = 16, 2¹⁰ = 1 024.

3-mashq (qiyin): Testda isbotlang

kurs/mashqlar/14/02-sinflar/sinflar.test.mjs faylida darsdagi binarySearch (qadam hisoblagichi bilan) va countCombos ni yozing. countCombos ga chaqiruvlar hisoblagichini qo'shing: u { count, calls } qaytarsin. Testlar (node:test):

1. binarySearch bo'sh massivda { index: -1, steps: 0 } qaytaradi (chegaraviy holat).
2. 1 000 ta saralangan raqamda topilmagan qiymat uchun qadamlar 11 dan oshmaydi, 1 000 000 tada — 21 dan.
3. countCombos 0 ta taomda 1 ta to'plam beradi (bo'sh to'plam ham to'plam!).
4. Taomlar bittaga ko'payganda chaqiruvlar soni taxminan ikki baravar oshadi (10 va 11 ta taom).

Ishora: chaqiruvlarni sanash uchun funksiya tashqarisida let calls = 0 va har chaqiruvda calls++; o'lchashdan oldin uni 0 ga qaytaring.

// kurs/mashqlar/14/02-sinflar/sinflar.test.mjs
import { test } from "node:test";
import assert from "node:assert/strict";

function binarySearch(sorted, target) {
  let left = 0;
  let right = sorted.length - 1;
  let steps = 0;
  while (left <= right) {
    steps++;
    const mid = Math.floor((left + right) / 2);
    if (sorted[mid] === target) return { index: mid, steps };
    if (sorted[mid] < target) left = mid + 1;
    else right = mid - 1;
  }
  return { index: -1, steps };
}

let calls = 0;
function combos(prices, budget, i = 0, sum = 0) {
  calls++;
  if (i === prices.length) return sum <= budget ? 1 : 0;
  return (
    combos(prices, budget, i + 1, sum + prices[i]) +
    combos(prices, budget, i + 1, sum)
  );
}

function countCombos(prices, budget) {
  calls = 0;
  const count = combos(prices, budget);
  return { count, calls };
}

const range = (n) => Array.from({ length: n }, (_, i) => i + 1);

test("bo'sh massiv — qadam yo'q", () => {
  assert.deepEqual(binarySearch([], 5), { index: -1, steps: 0 });
});

test("ming va million — log₂ n atrofida", () => {
  assert.ok(binarySearch(range(1000), 0).steps <= 11);
  assert.ok(binarySearch(range(1_000_000), 0).steps <= 21);
});

test("0 ta taom — bitta (bo'sh) to'plam", () => {
  assert.equal(countCombos([], 40000).count, 1);
});

test("+1 taom — chaqiruvlar ~2 baravar", () => {
  const prices = range(11).map((i) => i * 5000);
  const a = countCombos(prices.slice(0, 10), 40000).calls;
  const b = countCombos(prices, 40000).calls;
  assert.ok(b / a > 1.9 && b / a < 2.1, `nisbat: ${b / a}`);
});

✔ bo'sh massiv — qadam yo'q (1.2712ms)
✔ ming va million — log₂ n atrofida (43.3248ms)
✔ 0 ta taom — bitta (bo'sh) to'plam (0.2902ms)
✔ +1 taom — chaqiruvlar ~2 baravar (2.2754ms)
ℹ tests 4
ℹ suites 0
ℹ pass 4
ℹ fail 0
ℹ cancelled 0
ℹ skipped 0
ℹ todo 0
ℹ duration_ms 137.4411

4-mashq: Amaliy tajriba — jadvalga to'rt qator

kurs/mashqlar/14/MURAKKABLIK.md ga bugungi to'rt yechimni qo'shing: ikkiga bo'lib qidirish, toSorted bilan saralash, byudjetga sig'adigan to'plamlar va kuryerning hamma yo'llari. Yangi ustun ham qo'shing: "Amaliy chegara" — taxminan qaysi n gacha bir soniyada ishlaydi.

| Masala | Yechim | Vaqt | Amaliy chegara | Nega |
|---|---|---|---|---|
| Saralangan ro'yxatda qidirish | ikkiga bo'lib | O(log n) | istalgan | har qadam yarmini tashlaydi |
| Buyurtmalarni saralash | toSorted | O(n log n) | ~ mln | log n qatlam × n ish |
| Byudjetga sig'adigan to'plamlar | hamma to'plamlar | O(2ⁿ) | ~ 25 taom | har taom — 2 yo'l |
| Kuryer yo'li | hamma tartiblar | O(n!) | ~ 10 manzil | n × (n−1) × … × 1 |

git add 14/MURAKKABLIK.md 14/02-sinflar
git commit -m "14/02: murakkablik sinflari va amaliy chegaralar"

13. Real ishda

• Ma'lumotlar bazasi. Indeks — saralangan tuzilma; u qidiruvni O(n) dan O(log n) ga tushiradi. Million qatorli jadvalda bu "soniyalar" va "millisekundlar" farqi (Indeks nima).
• Frontend. Ro'yxatni saralash (sort) — O(n log n), har harf terilganda filtrlash — O(n). Ichma-ich sikl esa minglab element bilan sahifani qotiradi.
• Logistika va xaritalar. Yo'l tanlash masalalari tabiatan faktorial — shuning uchun real tizimlar taxminiy (heuristic) usullardan foydalanadi.
• Intervyu. "Bu yechimni O(n²) dan yaxshilay olasizmi?" — eng ko'p uchraydigan savol. Javob ko'pincha: saralash (n log n) yoki Set/Map (n).

Xulosa

• Yetti sinf, tezdan sekinga: O(1), O(log n), O(n), O(n log n), O(n²), O(2ⁿ), O(n!).
• log₂ n — n ni necha marta ikkiga bo'lsa bitta qoladi: ming — 10, million — 20, milliard — 30. Ikkiga bo'lib qidirish faqat saralangan ma'lumotda ishlaydi.
• Yaxshi saralash — O(n log n): log n qatlam × n ish. toSorted da solishtirishlar n · log₂ n ga yaqin chiqdi.
• O(2ⁿ) da bitta element vaqtni ikki baravar, O(n!) da — n baravar oshiradi. Ular faqat kichik n (≈ 25 va ≈ 10) uchun yaroqli.
• Masala chegarasidan kerakli sinfni taxmin qiling: n ≥ 100 000 bo'lsa — n log n yoki tezroq.

Keyingi dars: Kodning murakkabligini hisoblash — tayyor koddan Big-O'ni qanday chiqarish: ketma-ket qismlar qo'shiladi, ichma-ich sikllar ko'paytiriladi, rekursiya esa daraxt bo'lib sanaladi.

Manbalar

• Thomas H. Cormen va boshq., "Introduction to Algorithms", 4-nashr, MIT Press, 2022 — 3-bob.
• V8 blogi: "Getting things sorted in V8" (2018) — Array.prototype.sort TimSort'ga o'tgani — v8.dev/blog/array-sort
• MDN: Math.log2(), Array.prototype.toSorted() — developer.mozilla.org