Bo'lib-yech (divide and conquer): bo'lish, yechish va birlashtirish

Qisqacha: Bo'lib-yech (divide and conquer) — masalani mustaqil kichik qismlarga bo'lish, har qismni rekursiv yechish va javoblarni birlashtirish. Uning kuchi ikki joyda. Birinchisi: bitta yarim ikki marta kerak bo'lsa, uni bir marta hisoblash (tez daraja: n ta ko'paytirish o'rniga ≈ 2 log₂ n). Ikkinchisi: birlashtirishni aqlli qilish (eng yaqin juftlik: n² o'rniga ≈ n log² n). Murakkablik rekursiya daraxtidan o'qiladi: qavatlar soni × har qavatdagi ish. Merge sort — shu qolipning eng mashhur namunasi.

Bu darsda

• Bo'lib-yech qolipining uch qadamini ajrata olasiz va uni backtracking'dan farqlay olasiz.
• Rekursiya daraxtidan qavatlarni sanab, T(n) = 2T(n/2) + … ko'rinishidagi tenglamaning javobini topa olasiz.
• Tez darajaga ko'tarishni va ikki saralangan ro'yxatni birlashtirishni yoza olasiz.
• Eng yaqin juftlik masalasini O(n²) dan tezroq yechish g'oyasini tushuntira olasiz va o'lchov bilan tasdiqlaysiz.

Oldin bilishingiz kerak: Rekursiv fikrlash, Backtracking asoslari, Ikki ko'rsatkich, Kodning murakkabligini hisoblash.

1. Nega bu kerak?

Kun oxirida «Bahor» kassasida 2 000 ta chek bor. Jasur aka eng katta chekni bilmoqchi. Sardor ikki ofitsiantni chaqiradi: "Sen birinchi mingtasini ko'r, sen — ikkinchisini. Har biring o'z eng kattangni ayt". Keyin ikki javobdan kattasini oladi. Ofitsiantlar ham dangasalik qilib, o'z qismlarini yana ikkiga bo'lib, yordamchilariga berishadi...

Bu — bo'lib-yech (divide and conquer): katta ishni teng, mustaqil bo'laklarga bo'lish, har birini alohida bajarish va natijalarni yig'ish. Uch qadam:

1. Bo'lish (divide) — masalani bir xil turdagi kichikroq masalalarga ajratish, odatda ikki yarimga.
2. Yechish (conquer) — har kichik masalani rekursiv yechish; juda kichigini — to'g'ridan-to'g'ri.
3. Birlashtirish (combine) — kichik javoblardan katta javobni yig'ish.

Bu Rekursiv fikrlash darsidagi uch savolning o'zi. Farqi — kichik masalalar teng yarimlar va ular bir-biriga bog'liq emas. Bo'lib-yech backtracking dan ham farq qiladi: u yerda shoxlar turli tanlovlar edi va hammasi sinalardi; bu yerda har yarim javobning bir qismi va har biri bir martadan yechiladi.

Bugun to'rtta misolni ko'ramiz. Birinchisi tezlik bermaydi, lekin qolipni o'rgatadi. Qolgan uchtasi — bo'lib-yech nima uchun ixtiro qilinganini ko'rsatadi.

2. Qolip: eng katta chek

2.1 Kod va daraxt

Savdolarni (ming so'mda) yarimlarga bo'lib, eng kattasini topamiz. Massivni slice bilan kesmaymiz — faqat lo va hi indekslarini uzatamiz, nusxa olinmaydi:

Har tugunda lo..hi — shu chaqiruv qaraydigan oraliq, = son — u qaytargan javob. Barglarda bitta element: eng kichik holat. Ichki tugunlarda — bitta Math.max: birlashtirish.

2.2 Bu tezroqmi?

Yo'q. Daraxtda 7 ta barg va 6 ta ichki tugun, har birida O(1) ish — jami O(n). Oddiy sikl ham O(n) va undan soddaroq. Bo'lib-yech avtomatik tezlik bermaydi. U faqat ikki holatda yutadi:

• ikki yarimdan biri keraksiz yoki ikkalasi bir xil bo'lsa — ishni qisqartirish mumkin (tez daraja, ikkiga bo'lib qidirish);
• birlashtirish sodda usuldagi ishdan arzon bo'lsa (merge sort, eng yaqin juftlik).

Shunga qaramay, bu misolning ham foydasi bor: yarimlar mustaqil, demak ularni parallel — ikki protsessor yadrosida yoki ikki kompyuterda — bajarish mumkin. Katta ma'lumotlarni ko'p mashinada qayta ishlash (MapReduce g'oyasi) aynan shunday ishlaydi.

3. Rekursiya daraxtidan murakkablik

3.1 Qavatlarni sanash

Kodning murakkabligini hisoblash darsida qavatlar bo'yicha sanashni ko'rgan edik. Bo'lib-yech uchun u asosiy vosita. Ish vaqtini rekurrent tenglama bilan yozamiz — T(n) "n o'lchamli masala uchun ish" degani:

• maxOf: T(n) = 2 · T(n/2) + O(1) — ikki yarim va bitta solishtirish.
• Tez daraja: T(n) = T(n/2) + O(1) — bitta yarim va bir-ikki ko'paytirish.
• Merge sort: T(n) = 2 · T(n/2) + O(n) — ikki yarim va n elementli birlashtirish.

Tenglamani daraxt bilan yechamiz. Har qavatda masala o'lchami ikki baravar kichrayadi, shuning uchun qavatlar soni — log₂ n. Keyin har qavatdagi ishni qo'shamiz:

Hamma qatorda qavatlar soni bir xil — log₂ n.

Ikkinchi qatorda qavatlar ishi har safar ikki baravar oshadi (1 + 2 + 4 + … + n), yig'indi esa < 2n — xuddi amortizatsiya hisobidagidek. Uchinchi qatorda har qavat bir xil n ish qiladi, log n qavat — n log n. Bunday tenglamalarni bir qarashda yechadigan umumiy qoida asosiy teorema (master theorem) deb ataladi. Uni yodlash shart emas: daraxt chizib, qavatlarni qo'shsangiz kifoya.

Tekshirib ko'ring: Algoritm masalani uchta teng qismga bo'ladi, hammasini yechadi va O(n) ishda birlashtiradi: T(n) = 3T(n/3) + O(n). Jami murakkablik qanday?

4. Tez darajaga ko'tarish

4.1 Bitta yarim yetarli

Rekursiv fikrlash darsida power(x, n) = x · power(x, n - 1) yozdik — n ta ko'paytirish. Bo'lib-yech bilan boshqacha bo'lamiz: x¹⁰ = x⁵ · x⁵. Ikkala yarim bir xil — demak, x⁵ ni bir marta hisoblab, natijani o'ziga ko'paytirish kifoya. Toq daraja uchun bitta x ortiqcha: x¹³ = x⁶ · x⁶ · x.

let mults = 0;

function powerSlow(x, n) {
  let result = 1;
  for (let i = 0; i < n; i++) {
    result *= x;
    mults++;
  }
  return result;
}

function powerFast(x, n) {
  if (n === 0) return 1;
  // yarmini bir marta hisoblaymiz va natijani ikki marta ishlatamiz
  const half = powerFast(x, Math.floor(n / 2));
  mults++;
  if (n % 2 === 0) return half * half; // xⁿ = (xⁿᐟ²)²
  mults++;
  return half * half * x; // toq n: yana bitta x
}

for (const n of [10, 1000, 1000000]) {
  mults = 0;
  powerSlow(1.0000001, n);
  const slow = mults;
  mults = 0;
  powerFast(1.0000001, n);
  console.log(`n=${n}: oddiy ${slow}, tez ${mults} ko'paytirish`);
}
console.log(powerFast(2, 10), powerFast(3, 13)); // 1024 1594323

Konsolda:

n=10: oddiy 10, tez 6 ko'paytirish
n=1000: oddiy 1000, tez 16 ko'paytirish
n=1000000: oddiy 1000000, tez 27 ko'paytirish
1024 1594323

Million darajaga 27 ta ko'paytirish! n har safar ikki baravar kichrayadi — log₂ n ≈ 20 qavat, har qavatda bir yoki ikki ko'paytirish. T(n) = T(n/2) + O(1) — O(log n).

Hamma narsa bitta qatorga bog'liq: half o'zgaruvchisi. Agar return powerFast(x, n / 2) * powerFast(x, n / 2) yozsangiz, ikkala yarim alohida hisoblanadi — T(n) = 2T(n/2) + O(1) = O(n), yutuq yo'qoladi. Bir xil kichik masalani bir marta yechish — dinamik dasturlash g'oyasining kurtagi.

Bu usulning modul arifmetikasidagi varianti ((a * b) % m bilan) Sonlar nazariyasi asoslari darsida uchragan edi — kriptografiyada (HTTPS kalitlari) aynan shunday katta darajalar hisoblanadi.

5. Birlashtirish: merge sort'ga ko'prik

5.1 Ikki saralangan yarimni birlashtirish

Saralashning eng mashhur bo'lib-yech algoritmi — merge sort. Uning sirli qismi — birlashtirish: ikki saralangan ro'yxatdan bitta saralangan ro'yxat yasash. Bu Ikki ko'rsatkich usuli: har ro'yxat boshida ko'rsatkich, kichigini natijaga olamiz va o'sha ko'rsatkichni suramiz:

Har qadamda bitta element natijaga o'tdi — n element uchun ko'pi bilan n − 1 solishtirish: O(n). <= belgisiga e'tibor bering: teng elementlarda chapdagisi oldin olinadi. Bu kichik detal keyingi darsda "barqaror saralash" deb nomlanadi.

5.2 Butun algoritm

Birlashtirish tayyor bo'lsa, merge sort uch qatorga tushadi: ikkiga bo'l, har yarmini saralang, birlashtir:

function merge(left, right) {
  const result = [];
  let i = 0;
  let j = 0;
  while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) result.push(left[i++]);
    else result.push(right[j++]);
  }
  while (i < left.length) result.push(left[i++]);
  while (j < right.length) result.push(right[j++]);
  return result;
}

function mergeSort(nums) {
  if (nums.length <= 1) return nums; // bitta element — saralangan
  const mid = Math.floor(nums.length / 2);
  const left = mergeSort(nums.slice(0, mid)); // bo'lish va yechish
  const right = mergeSort(nums.slice(mid));
  return merge(left, right); // birlashtirish
}

console.log(mergeSort([35, 28, 30, 5, 12, 41, 8]).join(" "));

Konsolda:

5 8 12 28 30 35 41

T(n) = 2T(n/2) + O(n) — jadvaldagi uchinchi qator: O(n log n). Oddiy saralashlar (keyingi darslarda) O(n²); 100 000 elementda farq ming baravardan ko'p. Merge sort'ning xotirasi, barqarorligi va bog'langan ro'yxatda qo'llanishi — Merge sort darsida.

Tekshirib ko'ring: mergeSort 8 elementli massiv uchun nechta qavat chuqurlikka tushadi va har qavatda birlashtirishlar jami nechta elementni ko'chiradi?

6. Eng yaqin juftlik

6.1 Masala

«Bahor» kuryerlari kun davomida yuzlab manzilga boradi. Jasur aka ikki buyurtmani bitta yo'lda yetkazishni xohlaydi — eng avvalo, bir-biriga eng yaqin ikki manzilni topish kerak. Manzil — xaritadagi nuqta (x, y), kilometrda.

Sodda yechim: hamma juftlar orasidagi masofani hisoblash. n ta nuqta — n(n − 1) ÷ 2 juft, O(n²). 2 000 ta manzilda — ikki millionga yaqin masofa.

6.2 Bo'lib-yech g'oyasi

Nuqtalarni x bo'yicha saralab, vertikal chiziq bilan teng ikki yarimga bo'lamiz. Har yarimdagi eng yaqin juftni rekursiv topamiz. Ikkalasining kichigi — d. Lekin javob chiziq ustidan o'tgan juft ham bo'lishi mumkin: biri chapda, biri o'ngda. Uni qanday arzon topamiz?

Ikki kuzatish:

1. Bunday juft d dan yaqin bo'lsa, ikkala nuqta ham chiziqdan d dan kam uzoqda. Demak, faqat chiziq atrofidagi kengligi 2d yo'lak (strip) dagi nuqtalar qiziq.
2. Yo'lakdagi nuqtalarni y bo'yicha saralasak, har nuqtani faqat yuqorisidagi bir nechta (isbotlanganki, 7 tadan ko'p emas) qo'shnisi bilan solishtirish kifoya. Uzoqroqdagilar y bo'yicha d dan uzoq — demak, masofasi ham d dan katta.

Birinchi kuzatish bilan birlashtirishga faqat bir hovuch nuqta qoladi, ikkinchisi bilan har biri o'zgarmas sondagi qo'shnini ko'radi:

let checks = 0; // nechta masofa hisoblandi
function dist(a, b) {
  checks++;
  return Math.hypot(a.x - b.x, a.y - b.y);
}

function closestBrute(points) {
  let best = Infinity;
  for (let i = 0; i < points.length; i++) {
    for (let j = i + 1; j < points.length; j++) {
      best = Math.min(best, dist(points[i], points[j]));
    }
  }
  return best;
}

function closestPair(points) {
  const byX = points.toSorted((a, b) => a.x - b.x);
  function solve(lo, hi) {
    // [lo, hi) oraliq; kichik bo'lsa — sodda usul
    if (hi - lo <= 3) return closestBrute(byX.slice(lo, hi));
    const mid = Math.floor((lo + hi) / 2);
    const midX = byX[mid].x;
    const d = Math.min(solve(lo, mid), solve(mid, hi));
    // yo'lak: o'rta chiziqdan d dan yaqin nuqtalar, y bo'yicha
    const strip = byX
      .slice(lo, hi)
      .filter((p) => Math.abs(p.x - midX) < d)
      .sort((a, b) => a.y - b.y);
    let best = d;
    for (let i = 0; i < strip.length; i++) {
      for (let j = i + 1; j < strip.length; j++) {
        // y farqi best dan katta — yuqoriroqlari yanada uzoq
        if (strip[j].y - strip[i].y >= best) break;
        best = Math.min(best, dist(strip[i], strip[j]));
      }
    }
    return best;
  }
  return solve(0, byX.length);
}

// 2 000 ta yetkazish nuqtasi, 20×20 km hudud (urug'li generator)
let seed = 14;
const random = () =>
  (seed = (seed * 16807) % 2147483647) / 2147483647;
const points = Array.from({ length: 2000 }, () => ({
  x: random() * 20,
  y: random() * 20,
}));

checks = 0;
const a = closestBrute(points);
console.log(`sodda: ${a.toFixed(4)} km, ${checks} ta masofa`);
checks = 0;
const b = closestPair(points);
console.log(`bo'lib-yech: ${b.toFixed(4)} km, ${checks} ta masofa`);

Konsolda:

sodda: 0.0065 km, 1999000 ta masofa
bo'lib-yech: 0.0065 km, 2292 ta masofa

Bir xil javob — 6,5 metr (ikki manzil deyarli bir binoda). Lekin sodda usul ikki millionga yaqin masofa hisobladi, bo'lib-yech — atigi 2 292 ta. Yo'lakni har safar sort qilganimiz uchun birlashtirish O(n log n), jami O(n log² n). Bu yerda log² n — (log n)², ya'ni log n ning o'ziga ko'paytmasi: 16 000 nuqtada ≈ 14 × 14 ≈ 200. Yo'lakni ham merge sort kabi y bo'yicha birlashtirib borsak, O(n log n) gacha tushadi — lekin g'oya bir xil.

6.3 O'lchov

Ikkala usulni bir xil urug'li nuqtalar bilan o'lchadik (benchmarking darsidagi usul: har n alohida jarayonda, isitish, 5–7 o'lchov medianasi):

Sodda usulda n ikki baravar — vaqt to'rt baravar (×4,1, ×4,0, ×4,0): kvadratik. Bo'lib-yech'da — ikki baravardan sal ko'proq (×1,9 – ×2,2): n log² n. 16 000 manzilda farq 250 baravar, 64 000 manzil esa bir zumda — sodda usulda u taxminan bir daqiqa olardi.

7. Chegaraviy holatlar

• Bo'sh massiv. maxOf(nums, 0, -1) — lo > hi, eng kichik holat ushlamaydi va mid bilan cheksiz rekursiya boshlanadi. Bo'sh kirishni chaqiruvdan oldin tekshiring.
• Bitta element va ikki element. maxOf uchun bitta — eng kichik holat; ikkita — mid = lo, chap yarim 1, o'ng yarim 1 element. Oraliqlar doim kichrayadi.
• Toq uzunlik. 7 ta elementni mid 3 + 4 ga bo'ladi — yarimlar teng bo'lishi shart emas, faqat taxminan teng bo'lsin.
• Daraja 0 va manfiy daraja. powerFast(x, 0) — 1. Manfiy daraja uchun 1 / powerFast(x, -n) qiling; aks holda Math.floor(-1 / 2) = −1 va rekursiya to'xtamaydi.
• Bir xil nuqtalar. Ikki buyurtma bitta manzilda — masofa 0. Kod buni to'g'ri qaytaradi: 0 < d va yo'lak tekshiruvi ham to'xtamaydi.
• Ikki va undan kam nuqta. Bitta nuqtada juft yo'q — closestBrute Infinity qaytaradi. Bu ma'noli javob, lekin chaqiruvchi uni kutishi kerak.

8. Ko'p uchraydigan xatolar

8.1 Kichraymaydigan bo'lish

function maxOf(nums, lo, hi) {
  if (lo === hi) return nums[lo];
  const mid = Math.floor((lo + hi) / 2);
  const left = maxOf(nums, lo, mid - 1); // ❌ bo'sh bo'lishi mumkin
  const right = maxOf(nums, mid, hi); // ❌ ikki elementda — o'zi
  return Math.max(left, right);
}
console.log(maxOf([5, 8], 0, 1));

Konsolda:

RangeError: Maximum call stack size exceeded

Ikki element (lo = 0, hi = 1): mid = 0. Chap yarim maxOf(0, -1) — bo'sh, lo === hi hech qachon bo'lmaydi; o'ng yarim esa maxOf(0, 1) — xuddi o'zi. Ikkalasi ham cheksiz. Qoida: yarimlar [lo, mid] va [mid + 1, hi] — har biri bo'sh emas va asl oraliqdan qat'iy kichik.

8.2 Bir xil yarimni ikki marta hisoblash

powerFast(x, n / 2) * powerFast(x, n / 2) — yutuq yo'qoladi, O(log n) o'rniga O(n). Tuzatish: yarimni o'zgaruvchiga saqlang.

8.3 Birlashtirishda chegarani unutish

Eng yaqin juftlikda faqat ikki yarim javobini olib, yo'lakni tekshirmaslik — javob ba'zan noto'g'ri bo'ladi (eng yaqin juft chiziq ustida bo'lsa). Bunday xato kichik testlarda ko'pincha ko'rinmaydi. Tuzatish: tezkor algoritmni sodda (lekin ishonchli) algoritm bilan ko'p tasodifiy kirishda solishtiring — 3-mashqdagi kabi.

8.4 slice narxi

Har chaqiruvda nums.slice(...) qilish — har qavatda n ta element ko'chiriladi. maxOf uchun bu O(n) ni O(n log n) ga aylantiradi (Kodning murakkabligini hisoblash darsidagi yig'indi misoli). Imkon bo'lsa indekslarni uzating.

9. Mashqlar

1-mashq (oson): Ko'paytirishlarni sanang

Darsdagi powerFast x¹⁶ uchun nechta ko'paytirish qiladi (mults hisobi bo'yicha)? Daraxtni yozib chiqing: 16 → 8 → 4 → 2 → 1 → 0.

2-mashq (o'rta): Eng kichik va eng katta birga

Bitta bo'lib-yech funksiya bilan massivning eng kichik va eng katta elementini birga toping: minMax(nums, lo, hi) → [min, max]. Ikki elementli oraliqni eng kichik holat qiling (bitta solishtirish). 1 024 ta element uchun solishtirishlar sonini sanang va alohida Math.min + Math.max (2 × 1 023 = 2 046 solishtirish) bilan solishtiring.

let comparisons = 0;
function minMax(nums, lo, hi) {
  if (lo === hi) return [nums[lo], nums[lo]];
  if (hi === lo + 1) {
    comparisons++;
    return nums[lo] < nums[hi]
      ? [nums[lo], nums[hi]]
      : [nums[hi], nums[lo]];
  }
  const mid = Math.floor((lo + hi) / 2);
  const [minL, maxL] = minMax(nums, lo, mid);
  const [minR, maxR] = minMax(nums, mid + 1, hi);
  comparisons += 2;
  return [Math.min(minL, minR), Math.max(maxL, maxR)];
}

// 0..1023 sonlari aralash tartibda
const sales = Array.from(
  { length: 1024 },
  (_, i) => (i * 7919) % 1024,
);
console.log(minMax(sales, 0, sales.length - 1), comparisons);

[ 0, 1023 ] 1534

3-mashq (qiyin): Eng yaqin juftlik va tasodifiy testlar

kurs/mashqlar/14/26-bolib-yech/closest.test.mjs faylida darsdagi closestBrute va closestPair ni yozing. Testlar (node:test):

1. Ikki nuqta — ular orasidagi masofa; bitta nuqta — Infinity.
2. Bir xil ikki nuqta — 0.
3. Eng yaqin juft yarimlar chegarasida: x = 0, 1, 2, 2,1, 3, 4 (hammasi y = 0) — javob 0,1 bo'lsin.
4. Tasodifiy taqqoslash: 50 marta urug'li tasodifiy 200 nuqta yasang va ikkala funksiya javobi teng ekanini tekshiring.

// kurs/mashqlar/14/26-bolib-yech/closest.test.mjs
import { test } from "node:test";
import assert from "node:assert/strict";

const dist = (a, b) => Math.hypot(a.x - b.x, a.y - b.y);

function closestBrute(points) {
  let best = Infinity;
  for (let i = 0; i < points.length; i++) {
    for (let j = i + 1; j < points.length; j++) {
      best = Math.min(best, dist(points[i], points[j]));
    }
  }
  return best;
}

function closestPair(points) {
  const byX = points.toSorted((a, b) => a.x - b.x);
  function solve(lo, hi) {
    if (hi - lo <= 3) return closestBrute(byX.slice(lo, hi));
    const mid = Math.floor((lo + hi) / 2);
    const midX = byX[mid].x;
    const d = Math.min(solve(lo, mid), solve(mid, hi));
    const strip = byX
      .slice(lo, hi)
      .filter((p) => Math.abs(p.x - midX) < d)
      .sort((a, b) => a.y - b.y);
    let best = d;
    for (let i = 0; i < strip.length; i++) {
      for (let j = i + 1; j < strip.length; j++) {
        if (strip[j].y - strip[i].y >= best) break;
        best = Math.min(best, dist(strip[i], strip[j]));
      }
    }
    return best;
  }
  return solve(0, byX.length);
}

const pt = (x, y = 0) => ({ x, y });

test("ikki nuqta va bitta nuqta", () => {
  assert.equal(closestPair([pt(0, 0), pt(3, 4)]), 5);
  assert.equal(closestPair([pt(1, 1)]), Infinity);
});

test("bir xil nuqtalar — 0", () => {
  assert.equal(closestPair([pt(2, 2), pt(5, 1), pt(2, 2)]), 0);
});

test("eng yaqin juft chegarada", () => {
  const points = [0, 1, 2, 2.1, 3, 4].map((x) => pt(x));
  assert.ok(Math.abs(closestPair(points) - 0.1) < 1e-9);
});

test("tasodifiy: sodda usul bilan bir xil", () => {
  let seed = 2026;
  const random = () =>
    (seed = (seed * 16807) % 2147483647) / 2147483647;
  for (let round = 0; round < 50; round++) {
    const points = Array.from({ length: 200 }, () =>
      pt(random() * 20, random() * 20),
    );
    assert.equal(closestPair(points), closestBrute(points));
  }
});

✔ ikki nuqta va bitta nuqta (0.8637ms)
✔ bir xil nuqtalar — 0 (0.1488ms)
✔ eng yaqin juft chegarada (0.2161ms)
✔ tasodifiy: sodda usul bilan bir xil (30.5553ms)
ℹ tests 4
ℹ suites 0
ℹ pass 4
ℹ fail 0
ℹ cancelled 0
ℹ skipped 0
ℹ todo 0
ℹ duration_ms 116.283

4-mashq: Amaliy tajriba — murakkablik jadvali

kurs/mashqlar/14/MURAKKABLIK.md ga to'rt qator qo'shing: maxOf, tez daraja, merge sort va eng yaqin juftlik (sodda va bo'lib-yech). Har biriga rekurrent tenglamani ham yozing.

| Masala | Yechim | Vaqt | Xotira |
|---|---|---|---|
| Eng katta chek | bo'lib-yech, 2T(n/2)+O(1) | O(n) | O(log n) stek |
| Daraja xⁿ | tez, T(n/2)+O(1) | O(log n) | O(log n) stek |
| Saralash | merge sort, 2T(n/2)+O(n) | O(n log n) | O(n) |
| Eng yaqin juftlik | hamma juftlar | O(n²) | O(1) |
| Eng yaqin juftlik | bo'lib-yech + yo'lak | O(n log² n) | O(n) |

git add 14/MURAKKABLIK.md 14/26-bolib-yech
git commit -m "14/26: bo'lib-yech — tez daraja, eng yaqin juftlik testlari"

10. Real ishda

• Saralash va qidiruv. Merge sort, quick sort, ikkiga bo'lib qidirish — hammasi bo'lib-yech. V8 ichidagi sort (Node 24 da TimSort, yangi Chrome'da uning davomchisi PowerSort) ham merge sort g'oyasiga tayanadi (JS sort ichidan).
• Parallel hisoblash. Mustaqil yarimlar ko'p yadroga yoki ko'p serverga tarqatiladi: MapReduce, katta ma'lumot tizimlari, video kodlash. Brauzerda ham og'ir ishni bo'laklarga bo'lib, Web Workers yordamida parallel bajarish mumkin.
• Geometriya va xaritalar. Eng yaqin nuqtalar, xaritada "yaqin atrofdagi restoranlar" — fazoni bo'laklarga bo'ladigan tuzilmalar (k-d daraxt, quadtree) shu g'oyadan o'sgan.
• Kriptografiya. HTTPS ulanishida juda katta sonlarni katta darajaga ko'tarish — tez daraja bilan, aks holda bir kalit almashinuvi yillar olardi.
• Intervyu. "Pow(x, n)" (LeetCode 50), "Merge sort'ni yozing", "Count of inversions" — bo'lib-yech klassikasi (leetcode.com/problems/powx-n). Javobda rekurrent tenglamani aytish kuchli taassurot qoldiradi.

Xulosa

• Bo'lib-yech: bo'l → yech (rekursiv) → birlashtir. Yarimlar mustaqil va teng.
• Tezlik avtomatik emas: maxOf baribir O(n). Yutuq — bir xil yarimni bir marta hisoblashda yoki birlashtirish arzon bo'lganda.
• Murakkablik daraxtdan: qavatlar (log n) × qavat ishi. T(n/2) + O(1) → log n; 2T(n/2) + O(1) → n; 2T(n/2) + O(n) → n log n.
• Tez daraja: million darajaga 27 ta ko'paytirish. Birlashtirish ikki ko'rsatkich bilan O(n) — merge sort'ning yuragi.
• Eng yaqin juftlik: 2 000 nuqtada 1 999 000 o'rniga 2 292 masofa; 16 000 da ≈ 3,4 s o'rniga ≈ 13 ms.

Keyingi dars: Saralash tushunchalari — barqaror va beqaror saralash, joyida saralash, n log n quyi chegarasi va adaptiv saralash; vazifalar ga bir nechta kalitli saralash qo'shamiz.

Manbalar

• Thomas H. Cormen va boshq., "Introduction to Algorithms", 4-nashr, MIT Press, 2022 — 4-bob (bo'lib-yech, rekurrent tenglamalar, asosiy teorema), 33-bob (eng yaqin juftlik).
• Jon Kleinberg, Éva Tardos, "Algorithm Design", Pearson, 2005 — 5-bob ("Divide and Conquer", eng yaqin juftlik isboti).
• LeetCode: 50. Pow(x, n) — leetcode.com/problems/powx-n