Kodning murakkabligini hisoblash: sikllar, ichma-ich sikllar va rekursiya daraxti

Qisqacha: Koddan Big-O'ni chiqarish uchun to'rt qoida yetadi. Ketma-ket qismlar qo'shiladi va eng kattasi qoladi. Ichma-ich sikllar ko'paytiriladi. Ikki xil ma'lumot bo'lsa, ular alohida harf bilan yoziladi: O(a + b) yoki O(a · b). Rekursiyada esa chaqiruvlar daraxtini chizib, har qatlamdagi ishni qo'shamiz: har chaqiruv ikki chaqiruv qilsa — O(2ⁿ), har safar yarmiga tushsa — O(log n).

Bu darsda

• Sikl necha marta aylanishini qadamidan (i++, i += 2, i = i / 2) aniqlay olasiz.
• Ketma-ket va ichma-ich qismlardan umumiy Big-O'ni hisoblaysiz.
• Ikki xil kirish uchun O(a + b) va O(a · b) ni farqlaysiz.
• Rekursiv funksiya uchun chaqiruvlar daraxtini chizib, murakkablikni taxminlaysiz.

Oldin bilishingiz kerak: Big-O notatsiyasi, Asosiy murakkablik sinflari, Rekursiya asoslari, Execution context va call stack.

1. Nega bu kerak?

O'tgan darsda yettita sinfni ko'rdik va har birini o'lchadik. Lekin o'lchash uchun kodni ishga tushirish, katta ma'lumot yasash va kutish kerak. Haqiqiy ishda ko'pincha bunga vaqt yo'q.

Jasur aka Sardorga «Bahor» saytidagi beshta funksiyani berdi: "Qaysi biri mijozlar ko'payganda birinchi bo'lib qotadi?" Sardor har birini o'lchashni boshladi — bir kun ketdi. Tajribali dasturchi esa kodni o'qib, besh daqiqada javob beradi. U oddiy retsept bo'yicha ishlaydi: sikllarni topadi, ular necha marta aylanishini aniqlaydi va natijalarni qo'shadi yoki ko'paytiradi.

Bugun shu retseptni o'rganamiz. Keyin har qoidani o'lchov bilan tekshiramiz — retsept haqiqatan ishlashiga ishonch hosil qilish uchun.

2. Oddiy qadamlar va sikllar

2.1 O(1) qadamlar

Bitta o'zgaruvchiga qiymat berish, ikki sonni qo'shish, solishtirish, return, massivdan indeks bilan olish, Map.get — har biri O(1). Ularni alohida sanamaymiz: bitta funksiyada 3 ta yoki 30 ta bunday qadam bo'lsa ham, n ga bog'liq emas — O(1).

2.2 Sikl: necha marta aylanadi?

Siklning narxi = aylanishlar soni × bitta aylanishdagi ish. Ichida faqat O(1) qadamlar bo'lsa — narx aylanishlar soniga teng. Uchta siklni solishtiramiz:

function countLoops(n) {
  let every = 0;
  let everySecond = 0;
  let week = 0;
  for (let i = 0; i < n; i++) every++; // har bir buyurtma
  for (let i = 0; i < n; i += 2) everySecond++; // har ikkinchisi
  for (let day = 0; day < 7; day++) week++; // hafta kunlari
  return [every, everySecond, week];
}

console.log(countLoops(100)); // [ 100, 50, 7 ]
console.log(countLoops(1000)); // [ 1000, 500, 7 ]

Birinchi sikl n marta aylandi — O(n). Ikkinchisi n ÷ 2 marta — bu ham O(n): ÷ 2 — o'zgarmas ko'paytuvchi, birinchi qoida bo'yicha tashlanadi. Uchinchisi esa n qanday bo'lmasin, 7 marta — O(1)!

Bu muhim saboq: sikl ko'rinishi Big-O'ni aytmaydi. "Sikl bor — demak O(n)" — xato. Savol bitta: aylanishlar soni n ga bog'liqmi? Hafta kunlari, menyu bo'limlari (doim 5 ta), oyning kunlari bo'yicha sikl — O(1).

2.3 Ketma-ket qismlar qo'shiladi

Funksiyada ikki qism ketma-ket kelsa, ularning narxi qo'shiladi. Keyin dominant had qoladi (Big-O'ning ikkinchi qoidasi):

function prepareReport(orders) {
  const total = sumOrders(orders); // O(n) — bitta sikl
  const twins = findTwinOrders(orders); // O(n²) — hamma juftlar
  return { total, twins }; // O(1)
}
// Jami: O(n) + O(n²) + O(1) = O(n²)

Bu parcha: sumOrders va findTwinOrders — o'tgan darslardagi kabi funksiyalar. Hisobotni tezlashtirmoqchi bo'lsangiz, sumOrders ga tegishning foydasi yo'q — butun vaqtni findTwinOrders yeydi. Retseptdan amaliy xulosa: eng qimmat qismni toping va o'shani yaxshilang.

Tekshirib ko'ring: Funksiyada uchta ketma-ket sikl bor, har biri n marta aylanadi. Big-O qanday?

3. Ichma-ich sikllar ko'paytiriladi

3.1 Jadval kabi

Sikl ichida sikl bo'lsa, tashqi siklning har aylanishida ichki sikl to'liq aylanadi. Shuning uchun narxlar ko'paytiriladi: tashqi n marta × ichki n marta = n². Buni jadval deb tasavvur qiling: qatorlar — tashqi sikl, ustunlar — ichki sikl, har katak — bitta qadam.

Takroriy buyurtmalar funksiyasida ichki sikl j = i + 1 dan boshlanadi, ya'ni har safar kamroq aylanadi. Jadvalning qaysi kataklari ko'rilishini kuzating:

Ichki sikl 4, 3, 2, 1 va 0 marta aylandi. Jami 10 — jadvalning yarmiga yaqin. Ichki sikl "kamayib" borsa ham, natija baribir taxminan n² ÷ 2, ya'ni O(n²). Yarmi — o'zgarmas ko'paytuvchi.

3.2 Uch qavat — n³

Uchta ichma-ich sikl — n × n × n = n³ (n kub). Misol: «Bahor» uchun kombo-tushlik — har taom, har ichimlik va har shirinlikning hamma uchliklari, hammasi bitta n ta ro'yxatdan. Bunday sikl n = 1 000 da milliard qadam qiladi. Uch qavatli siklni ko'rsangiz, deyarli har doim yaxshiroq yo'l izlash kerak.

3.3 Ichki sikl yarimlab borsa

Ichki siklning qadami ham muhim. Bu sikl i ni har safar ikkiga bo'ladi:

function countHalvingLoop(n) {
  let steps = 0;
  for (let i = n; i > 1; i = Math.floor(i / 2)) {
    steps++;
  }
  return steps;
}

function countNLogN(n) {
  let steps = 0;
  for (let i = 0; i < n; i++) {
    for (let j = n; j > 1; j = Math.floor(j / 2)) {
      steps++; // ichki sikl — log₂ n marta
    }
  }
  return steps;
}

for (const n of [1024, 2048]) {
  console.log(n, countHalvingLoop(n), countNLogN(n));
}

Konsolda:

1024 10 10240
2048 11 22528

Yarimlab boruvchi sikl — menyu kitobi o'yini: log₂ n marta, ya'ni O(log n). n ikki baravar oshdi — sikl faqat bitta aylanishga uzaydi (10 → 11). Uni oddiy sikl ichiga qo'ysak — n × log₂ n = O(n log n): 10 240 va 22 528.

Qoida: sikl o'zgaruvchisi qo'shilib borsa (i++, i += 2) — aylanishlar n ga proporsional. Ko'paytirilib yoki bo'linib borsa (i *= 2, i = i / 2) — log n.

Tekshirib ko'ring: for (let i = 1; i < n; i *= 3) necha marta aylanadi? Big-O qanday?

4. Ikki xil kirish: O(a + b) va O(a · b)

4.1 Har birini o'z harfi bilan

Hozirgacha bitta n bor edi. Lekin ko'p funksiyalar ikki xil ma'lumot oladi: menyu va buyurtmalar, taomlar va ichimliklar. Ularning hajmi bog'liq emas: menyuda 30 ta taom, buyurtmalar esa 100 000 ta bo'lishi mumkin. Ikkalasini bitta n deb yozish — xato. Ularga alohida harf beramiz: a va b.

Kombo-menyu: har taom har ichimlik bilan juftlanadi:

function makeCombos(dishes, drinks) {
  const combos = [];
  for (const dish of dishes) {
    for (const drink of drinks) {
      combos.push(`${dish} + ${drink}`);
    }
  }
  return combos;
}

const dishes = ["osh", "manti", "lag'mon"];
const combos = makeCombos(dishes, ["ko'k choy", "ayron"]);
console.log(combos.length); // 6
console.log(combos[0]); // osh + ko'k choy

3 ta taom × 2 ta ichimlik = 6 ta kombo. a ta taom va b ta ichimlik — a × b qadam: O(a · b). O(n²) emas! Ichimliklar 2 ta bo'lib qolsa, ish taomlar soniga chiziqli bog'liq.

Agar ikki qism ketma-ket kelsa — qo'shiladi: avval hamma taomlarni chiqarish (a), keyin hamma ichimliklarni (b) — O(a + b). Bu yerda dominant hadni tanlab bo'lmaydi: qaysi biri katta ekanini bilmaymiz. Ikkalasi ham qoladi.

4.2 Amaliy misol: buyurtmalarni tekshirish

Kun oxirida Sardor har buyurtmadagi taom menyuda borligini tekshiradi. Menyu — a ta taom, buyurtmalar — b ta. Ikki yechim:

// 1-yechim: har buyurtma uchun menyuda chiziqli qidiruv
function countUnknownSlow(menu, orders) {
  let unknown = 0;
  for (const order of orders) { // b marta
    if (!menu.includes(order)) unknown++; // includes — a qadam
  }
  return unknown; // O(a · b)
}

// 2-yechim: avval menyudan Set, keyin tez tekshiruv
function countUnknownFast(menu, orders) {
  const known = new Set(menu); // a qadam
  let unknown = 0;
  for (const order of orders) { // b marta
    if (!known.has(order)) unknown++; // O(1)
  }
  return unknown; // O(a + b)
}

Birinchisida includes sikl ichida — yashirin ichma-ich sikl. U bitta qator, lekin har chaqiruvda menyuni boshidan ko'radi. Ikkinchisida ikkita ketma-ket qism: Set yasash (a) va tekshiruv (b).

4.3 O'lchov

Retsept bashorat qiladi: birinchi yechimda b ni ikki baravar oshirsak — vaqt ikki baravar; a va b ni birga oshirsak — to'rt baravar. Ikkinchisida ikkalasini oshirsak — atigi ikki baravar. Tekshiramiz (yarim buyurtmalar menyuda yo'q):

includes ustunida b ikki baravar oshdi — vaqt ham ikki baravar (10 → 21 ms). Keyin menyu ham ikki baravar kattalashdi — yana 2,6 baravar. Demak, a va b birga ikki baravar oshganda vaqt taxminan 5 baravar oshdi. Retsept 4 deydi; ortiqchasi — katta menyuda har qidiruv xotira tufayli biroz sekinroq. Set ustunida esa a va b birga ikki baravar oshganda vaqt atigi ≈ 2,2 baravar oshdi (0,36 → 0,79). Eng katta holatda ikki yechim orasidagi farq — taxminan 75 baravar, va ma'lumot o'sgan sari u o'sib boradi.

Diqqat: Yashirin sikllar faqat includes da emas. indexOf, find, filter, slice, spread ([...arr]), Object.keys — hammasi butun ma'lumotni ko'radi. Sikl ichida ularni ko'rsangiz, narxini ko'paytiring. Har bir o'rnatilgan amalning narxini JS o'rnatilgan amallarining narxi darsida jadval qilib chiqamiz.

5. Rekursiya: chaqiruvlar daraxti

5.1 Bitta chaqiruv — zanjir

Rekursiyada sikl yo'q, lekin takrorlanish bor — funksiya o'zini chaqiradi. Uni sanash uchun savol: jami nechta chaqiruv bo'ladi va har birida qancha ish?

Eng oddiy holat: funksiya o'zini bir marta, n ni bittaga kamaytirib chaqiradi — sumTo(n) → sumTo(n - 1) → … → sumTo(0). Bu zanjir: n + 1 ta chaqiruv, har birida O(1) ish — jami O(n). Sikl bilan bir xil.

5.2 Ikki chaqiruv — daraxt

Fibonachchi sonlari: har son oldingi ikkitasining yig'indisi (0, 1, 1, 2, 3, 5, 8, …). Sodda rekursiv yechim o'zini ikki marta chaqiradi. Chaqiruvlarni daraxt qilib chizamiz. Har tugun — bitta chaqiruv, undagi raqam — n. Pastda — chaqiruvlar steki: hozir qaysi chaqiruvlar "ochiq":

fib(5) uchun 15 ta chaqiruv bo'ldi. Daraxtning har qatlamida chaqiruvlar soni deyarli ikki baravar ko'payadi: 1, 2, 4, 6, 2. Chuqurlik — taxminan n. Har chaqiruv ikki chaqiruv qilsa va chuqurlik n bo'lsa, eng ko'pi bilan 2ⁿ ta tugun bo'ladi — O(2ⁿ). Sanab ko'ramiz:

let calls = 0;
function fib(n) {
  calls++;
  if (n < 2) return n;
  return fib(n - 1) + fib(n - 2);
}

for (const n of [10, 20, 30]) {
  calls = 0;
  fib(n);
  console.log(`fib(${n}): ${calls} chaqiruv`);
}

Konsolda:

fib(10): 177 chaqiruv
fib(20): 21891 chaqiruv
fib(30): 2692537 chaqiruv

n 10 ga oshdi — chaqiruvlar 120 baravardan ko'p oshdi. Vaqtni ham o'lchadik (har n alohida jarayonda, mediana):

Har qadamda vaqt taxminan 1,6 baravar oshdi — 2 emas. Sababi daraxtning shaklida: o'ng shox (n - 2) chapdagidan kaltaroq, daraxt to'liq emas. O(2ⁿ) — yuqori chegara: "bundan tez o'smaydi" degani. Big-O aynan shunday ishlatiladi — kafolat sifatida. Aniqroq hisob 1,618ⁿ ni beradi (bu son "oltin nisbat" deb ataladi), lekin amaliy xulosa bir xil: eksponensial, n = 50 da allaqachon soatlab hisoblaydi.

Daraxtga yana qarang: fib(2) uch marta, fib(3) ikki marta qayta hisoblandi. Natijalarni eslab qolishni Memoization darsida o'rgangan edik — har fib(k) bir marta hisoblansa, chaqiruvlar n atrofida qoladi va murakkablik O(n) ga tushadi. Bu g'oya Dinamik dasturlash ning asosi.

5.3 Yarmiga tushadigan rekursiya

Agar rekursiv chaqiruv masalani yarmiga kamaytirsa — daraxt emas, kalta zanjir: n, n ÷ 2, n ÷ 4, …, 1. Ikkiga bo'lib qidirishning rekursiv varianti shunday: har chaqiruvda o'zini bir marta, yarim oyna bilan chaqiradi. Chaqiruvlar soni — log₂ n, har birida O(1) ish — O(log n).

6. Qatlamlar bo'yicha sanash

6.1 Ikkiga bo'lib, har qatlamda n ish

Endi murakkabroq holat: funksiya o'zini ikki marta chaqiradi, lekin har safar yarim ma'lumot bilan, va har chaqiruvda biroz ish qiladi. Narxlar yig'indisini shunday hisoblaymiz: ro'yxatni ikkiga slice bilan bo'lamiz, har yarmini alohida yig'amiz. slice — nusxa oladi, ya'ni har elementni ko'chiradi. Ko'chirilgan elementlarni sanaymiz:

let copied = 0;
function sumHalves(prices) {
  if (prices.length <= 1) return prices[0] ?? 0;
  const mid = Math.floor(prices.length / 2);
  const left = prices.slice(0, mid); // nusxa
  const right = prices.slice(mid); // nusxa
  copied += prices.length;
  return sumHalves(left) + sumHalves(right);
}

for (const n of [8, 1024, 4096]) {
  copied = 0;
  const prices = Array.from({ length: n }, () => 5000);
  const total = sumHalves(prices);
  console.log(`n=${n}: jami ${total}, nusxa ${copied}`);
}

Konsolda:

n=8: jami 40000, nusxa 24
n=1024: jami 5120000, nusxa 10240
n=4096: jami 20480000, nusxa 49152

prices[0] ?? 0 — bo'sh ro'yxatda prices[0] undefined, ?? uni 0 ga almashtiradi (?? va ?.). 8 ta narx — 24 ta nusxa = 8 × 3. 1024 — 10 240 = 1024 × 10. Bu n × log₂ n!

Nega? Daraxtni qatlam bo'yicha sanang. Eng tepada bitta chaqiruv 8 ta elementni nusxalaydi. Ikkinchi qatlamda ikkita chaqiruv, har biri 4 tadan — yana 8. Uchinchida to'rtta chaqiruv, 2 tadan — yana 8. Har qatlamda jami n ish, qatlamlar esa log₂ n ta (yarimlash). Jami: n × log₂ n = O(n log n). Bu merge sort ning ham aynan shu hisobi.

O'lchov ham buni tasdiqladi. Narxlar ikki baravar ko'payganda vaqt taxminan ikki baravar oshdi: 100 000 narx — ≈ 6,1 ms, 200 000 — ≈ 12,5 ms, 400 000 — ≈ 25 ms, 800 000 — ≈ 53 ms. Bu n log n uchun kutilgan natija — ikki baravardan biroz ko'proq.

6.2 Master teorema intuitsiyasi

Algoritm kitoblarida bunday rekursiyalar uchun tayyor formula bor — master teorema (master theorem). Formulasiz, uning g'oyasi shunday: daraxtni qatlamlarga bo'lib, har qatlamdagi jami ishni solishtiring.

Uchta holatni eslab qoling. Ish qatlamdan qatlamga teng qolsa — bitta qatlam ishi × qatlamlar soni. Ish pastga qarab kamaysa — eng tepadagi qatlam hal qiladi (uchinchi qator: n + n ÷ 2 + n ÷ 4 + … yig'indisi 2n dan oshmaydi). Ish pastga qarab ko'paysa — eng pastki qatlam hal qiladi. U yerdagi chaqiruvlar o'zidan boshqa chaqiruv qilmaydi (daraxtning "barglari"), ular esa 2ⁿ ta bo'lishi mumkin.

Tekshirib ko'ring: Funksiya o'zini uch marta chaqiradi, har safar n − 1 bilan, va har chaqiruvda O(1) ish qiladi. Taxminan nechta chaqiruv bo'ladi?

7. Retsept — bir sahifada

flowchart TD
  A["Funksiyani oling"] --> B{"Sikl yoki rekursiya bormi?"}
  B -- "yo'q" --> C["O(1)"]
  B -- "sikl" --> D["Aylanishlar n ga bog'liqmi?<br/>i++ → n, i*2 → log n"]
  D --> E["Ichma-ich — ko'paytiring<br/>ketma-ket — qo'shing"]
  B -- "rekursiya" --> F["Daraxt chizing:<br/>qatlamlar × qatlam ishi"]
  E --> G["Yashirin sikllar:<br/>includes, slice, spread"]
  F --> H["Dominant hadni qoldiring"]
  G --> H

Diagrammani chapdan o'ngga emas, tepadan pastga o'qing: har funksiya shu yo'ldan o'tadi. Oxirgi qadam doim bir xil — o'zgarmas sonlarni va kichik hadlarni tashlash.

8. Ko'p uchraydigan xatolar

8.1 Har siklni n deb hisoblash

Hafta kunlari, menyu bo'limlari yoki "eng ko'pi bilan 3 urinish" bo'yicha sikl — O(1). Tuzatish: har sikl uchun "aylanishlar soni ma'lumot hajmiga bog'liqmi?" deb so'rang.

8.2 Ikki xil kirishni bitta n ga aylantirish

makeCombos(dishes, drinks) ni "O(n²)" deyish — noto'g'ri, chunki ichimliklar 2 ta bo'lsa, ish chiziqli. Tuzatish: har mustaqil ma'lumotga o'z harfini bering: O(a · b).

8.3 Yashirin siklni ko'rmaslik

for ichida includes, indexOf, slice yoki [...arr] — bu ichma-ich sikl. Tuzatish: o'rnatilgan metodlarning narxini biling (JS o'rnatilgan amallarining narxi).

8.4 Rekursiya chuqurligini chaqiruvlar soni bilan chalkashtirish

fib(30) ning chuqurligi atigi 30, lekin chaqiruvlar 2,7 million. Vaqt — chaqiruvlar soniga, stek xotirasi esa chuqurlikka bog'liq. Bu farqni keyingi darsda ko'ramiz.

9. Mashqlar

1-mashq (oson): Retseptni qo'llang

Har funksiya uchun Big-O'ni yozing (n — orders uzunligi):

// (a)
for (let i = 0; i < orders.length; i++) {
  for (let k = 0; k < 3; k++) { /* uch xil soliq */ }
}
// (b)
for (let i = 1; i < orders.length; i *= 2) { /* ... */ }
// (c)
for (const order of orders) {
  const first = orders.indexOf(order);
  if (first !== orders.lastIndexOf(order)) { /* takror */ }
}
// (d)
for (const order of orders) { /* ... */ }
for (const order of orders) {
  for (let i = orders.length; i > 1; i = Math.floor(i / 2)) {}
}

2-mashq (o'rta): Ikki harf bilan

Menyuda a ta taom, omborda b ta mahsulot. Funksiya har taom uchun uning retseptidagi 5 ta mahsulotni ombordan find bilan qidiradi. Big-O qanday? Uni qanday tezlashtirish mumkin va unda Big-O qanday bo'ladi? Avval sonlar bilan sanang: a = 30 taom, b = 1000 mahsulot. Eng yomon holatda sekin yechim [:150000] qadam qiladi (30 × 5 × 1000). Ombordan bir marta Map yasab, keyin get bilan olsa — [:1150] qadam (1000 + 30 × 5).

3-mashq (qiyin): Retseptni test bilan tekshiring

kurs/mashqlar/14/03-hisoblash/hisob.test.mjs faylida darsdagi uch funksiyaning hisoblagichli variantlarini yozing: countHalvingLoop(n), countNLogN(n) va makeCombos o'rniga countCombos(a, b) (faqat sanaydi). Testlar retsept bashoratini tekshirsin:

1. countHalvingLoop: n ikki baravar oshganda qadam aynan bittaga oshadi (1024 va 2048).
2. countNLogN(1024) = 1024 × 10.
3. countCombos(a, b): b ni ikki baravar oshirsa — natija ikki baravar; a va b ni ikki baravar — to'rt baravar.
4. Chegaraviy: n = 1 va n = 0 da countHalvingLoop 0 qaytaradi.

// kurs/mashqlar/14/03-hisoblash/hisob.test.mjs
import { test } from "node:test";
import assert from "node:assert/strict";

function countHalvingLoop(n) {
  let steps = 0;
  for (let i = n; i > 1; i = Math.floor(i / 2)) steps++;
  return steps;
}

function countNLogN(n) {
  let steps = 0;
  for (let i = 0; i < n; i++) steps += countHalvingLoop(n);
  return steps;
}

function countCombos(a, b) {
  let steps = 0;
  for (let i = 0; i < a; i++) {
    for (let j = 0; j < b; j++) steps++;
  }
  return steps;
}

test("yarimlash: n×2 → +1 qadam", () => {
  assert.equal(countHalvingLoop(2048) - countHalvingLoop(1024), 1);
});

test("n log n: 1024 × 10", () => {
  assert.equal(countNLogN(1024), 10240);
});

test("a·b: b×2 → ×2, a×2 va b×2 → ×4", () => {
  const base = countCombos(30, 100);
  assert.equal(countCombos(30, 200), base * 2);
  assert.equal(countCombos(60, 200), base * 4);
});

test("chegaraviy: 0 va 1", () => {
  assert.equal(countHalvingLoop(0), 0);
  assert.equal(countHalvingLoop(1), 0);
});

✔ yarimlash: n×2 → +1 qadam (0.7285ms)
✔ n log n: 1024 × 10 (0.4004ms)
✔ a·b: b×2 → ×2, a×2 va b×2 → ×4 (0.502ms)
✔ chegaraviy: 0 va 1 (0.1024ms)
ℹ tests 4
ℹ suites 0
ℹ pass 4
ℹ fail 0
ℹ cancelled 0
ℹ skipped 0
ℹ todo 0
ℹ duration_ms 90.4543

4-mashq: Amaliy tajriba — fib qatori

kurs/mashqlar/14/MURAKKABLIK.md ga ikki qator qo'shing: rekursiv fib (O(2ⁿ), aniqrog'i ~1,6ⁿ) va Memoization darsidagi eslab qoluvchi variant. Memo variantning Big-O'sini o'zingiz hisoblang: har fib(k) necha marta haqiqatan hisoblanadi? Keyin calls hisoblagichi bilan fib(30) uchun ikkalasini solishtiring.

| Masala | Yechim | Vaqt | Amaliy chegara | Nega |
|---|---|---|---|---|
| Fibonachchi | sodda rekursiya | O(2ⁿ) | ~ n = 40 | har chaqiruv — 2 chaqiruv |
| Fibonachchi | memo bilan | O(n) | ~ n = 1000 | har fib(k) bir marta |

git add 14/MURAKKABLIK.md 14/03-hisoblash
git commit -m "14/03: murakkablikni hisoblash testlari, fib qatori"

10. Real ishda

• Kod ko'rib chiqish. "Bu funksiya sikl ichida find qilyapti, ro'yxat qancha bo'lishi mumkin?" — eng ko'p qoldiriladigan izohlardan biri. Retsept besh daqiqada javob beradi.
• Ma'lumotlar bazasi so'rovlari. "Har buyurtma uchun alohida so'rov" (N+1 muammo) — aynan yashirin ichma-ich sikl, faqat har qadami tarmoq orqali. Buni backend qismida ko'ramiz.
• Intervyu. Yechimni yozgandan keyin "murakkabligi qanday?" savoliga retsept bilan javob berasiz: "tashqi sikl n, ichida Set.has O(1) — jami O(n); qo'shimcha xotira O(n)". Oxirgi qismni keyingi darsda o'rganamiz.

Xulosa

• Sikl narxi = aylanishlar soni × ichidagi ish. i++ — n marta, i *= 2 — log n marta, day < 7 — O(1).
• Ketma-ket qismlar qo'shiladi, ichma-ich qismlar ko'paytiriladi; keyin dominant had qoladi.
• Ikki mustaqil kirish — ikki harf: O(a + b) yoki O(a · b); ularni bitta n ga aylantirmang.
• includes, indexOf, slice, spread sikl ichida — yashirin ichma-ich sikl.
• Rekursiyani daraxt qilib chizing: har qatlam ishi × qatlamlar. Ikki chaqiruv va n − 1 — O(2ⁿ) (fib'da ~1,6ⁿ); ikki chaqiruv, yarim va n ish — O(n log n).

Keyingi dars: Xotira murakkabligi, eng yomon holat va amortizatsiya — vaqt bilan birga xotira ham o'lchanadi, rekursiya stek joyini yeydi, push esa "o'rtacha" arzon.

Manbalar

• Thomas H. Cormen va boshq., "Introduction to Algorithms", 4-nashr, MIT Press, 2022 — 2.3 (merge sort tahlili), 4-bob (rekursiv tenglamalar va master teorema).
• MDN: Array.prototype.includes(), Array.prototype.slice() — developer.mozilla.org