Greedy algoritmlar: har qadamda eng yaxshi tanlov — qachon to'g'ri, qachon adashtiradi

Qisqacha: Greedy (ochko'z) algoritm har qadamda hozir eng yaxshi ko'ringan tanlovni qiladi va unga qaytmaydi. Bu tez va sodda: ko'pincha O(n) yoki O(n log n). Lekin har masalada ham to'g'ri emas — "eng katta kupyura" qoidasi «Bahor» kassasida ishlaydi, {4, 3, 1} tangalarida esa adashadi. Shuning uchun greedy yechim yozilgach, uni qarshi misol bilan tekshirish kerak: sodda yoki DP yechim bilan ko'p kirishda solishtiriladi.

Bu darsda

• Greedy tanlov nima ekanini tushuntirasiz va uni DP dan farqlaysiz.
• Greedy yechimni sodda yechim bilan solishtirib, qarshi misolni avtomatik topasiz.
• Jump game va gas station masalalarini O(n) da yechasiz va nega to'g'ri ishlashini tushuntira olasiz.
• Huffman kodlash g'oyasini — ikki eng kamini birlashtirishni — daraxtda kuzatasiz.

Oldin bilishingiz kerak: 2D DP masalalari, 1D DP masalalari, Heap, Daraxt atamalari va binar daraxt.

1. Nega bu kerak?

O'tgan darsda Dilshod akaga 35 000 so'mga taom tanladik. Xayolga birinchi kelgan javob — eng yoqimli taom, osh. Lekin to'g'ri javob manti va ko'k choy bo'lib chiqdi. "Hozir eng yaxshisini olish" bu safar adashtirdi.

Endi boshqa vaziyat. «Bahor» kassasida mijoz 100 000 so'm berdi, hisob — 63 000. Qaytim 37 000. Kassir o'ylamasdan, eng katta kupyuradan boshlab beradi: 20 000, 10 000, 5 000, 2 000. To'rtta kupyura — undan kam bo'lmaydi. Bu safar "hozir eng yaxshisini olish" to'g'ri chiqdi.

Bu ikki usulning nomi bor: greedy (ochko'z) algoritm. U xuddi och odam kabi ishlaydi: dasturxondagi eng mazali ko'ringan taomni oladi va oldinga qaramaydi. Ba'zan bu eng yaxshi tushlik bo'ladi, ba'zan esa yo'q. Bugun ikki savolga javob beramiz: greedy qachon ishlaydi va buni qanday tekshirish mumkin?

Maslahat: "Ochko'z" so'zini regex quantifierlar darsida ham ko'rgan edik: .* imkon qadar ko'p belgi oladi. G'oya bir xil — hozir iloji boricha ko'p olish.

2. Greedy tanlov: qaytim berish

2.1 Kassir algoritmi

Sardor kassa dasturiga qaytim hisobini qo'shdi. Kassada 50 000, 20 000, 10 000, 5 000, 2 000 va 1 000 so'mlik kupyuralar bor:

const BILLS = [50000, 20000, 10000, 5000, 2000, 1000];

function makeChange(amount, bills = BILLS) {
  const result = [];
  for (const bill of bills) { // kattadan kichikka
    while (amount >= bill) {
      result.push(bill); // eng katta sig'adiganini olamiz
      amount -= bill;
    }
  }
  return amount === 0 ? result : null; // qaytarib bo'lmadi
}

console.log(makeChange(37000)); // [ 20000, 10000, 5000, 2000 ]
console.log(makeChange(87000).length); // 5
console.log(makeChange(1500)); // null

Har qadamda bitta tanlov: "hozir sig'adigan eng katta kupyura". Tanlov qilingach, unga qaytilmaydi. Mana shu ikki belgi — greedy tanlov: mahalliy (hozirgi) eng yaxshi qaror va orqaga qaytmaslik. 1 500 so'mga null qaytdi: kassada 500 so'mlik yo'q.

Murakkablik: k ta kupyura turi va har biridan bir nechta — O(k + javobdagi kupyuralar soni). Kupyura turlari o'zgarmas (6 ta), shuning uchun amalda O(1).

2.2 Qarshi misol

Endi xayoliy mamlakatni olaylik: u yerda tangalar 1, 3 va 4 so'mlik. 6 so'm qaytarish kerak. Greedy eng kattasidan boshlaydi: 4, keyin 1, yana 1 — uchta tanga. Lekin 3 + 3 — ikkita tanga! Greedy adashdi.

Greedy noto'g'ri ekanini ko'rsatish uchun bitta qarshi misol (counterexample) yetadi — qoida buziladigan bitta aniq kirish. To'g'ri ekanini ko'rsatish esa qiyinroq: buning uchun isbot yoki juda ko'p tekshiruv kerak. Qarshi misolni qo'lda qidirish uzoq — kompyuter buni tezroq qiladi.

2.3 Qarshi misolni avtomatik qidirish

G'oya: greedy javobini aniq to'g'ri yechim bilan solishtiramiz. Aniq yechim — 1D DP masalalari dagi tangalar masalasi: har summa uchun eng kam tangalar soni. U sekinroq, lekin hamma variantni hisobga oladi:

function greedyCount(amount, coins) {
  let count = 0;
  for (const coin of coins) { // coins — kattadan kichikka
    count += Math.floor(amount / coin);
    amount %= coin;
  }
  return amount === 0 ? count : Infinity;
}

function dpCount(amount, coins) {
  const best = Array(amount + 1).fill(Infinity);
  best[0] = 0;
  for (let a = 1; a <= amount; a++) {
    for (const coin of coins) {
      if (coin <= a) best[a] = Math.min(best[a], best[a - coin] + 1);
    }
  }
  return best[amount];
}

function findCounterexample(coins, maxAmount) {
  for (let a = 1; a <= maxAmount; a++) {
    const g = greedyCount(a, coins);
    const d = dpCount(a, coins);
    if (g !== d) return { amount: a, greedy: g, best: d };
  }
  return null; // shu oraliqda qarshi misol yo'q
}

console.log(findCounterexample([4, 3, 1], 50));
console.log(findCounterexample([10, 7, 1], 50));
console.log(findCounterexample([50, 20, 10, 5, 2, 1], 500));

Konsolda:

{ amount: 6, greedy: 3, best: 2 }
{ amount: 14, greedy: 5, best: 2 }
null

{4, 3, 1} da eng kichik qarshi misol — 6. {10, 7, 1} da — 14: greedy 10 + 1 + 1 + 1 + 1 (5 ta), to'g'risi 7 + 7 (2 ta). «Bahor» kupyuralari (ming so'mda) uchun 500 gacha qarshi misol topilmadi.

"500 gacha yo'q" — bu hali "hech qachon yo'q" degani emas. Bu yerda matematika yordam beradi. Kozen va Zaks 1994-yilda isbotlagan: agar qarshi misol bor bo'lsa, eng kichigi ikki eng katta tanga yig'indisidan kichik. «Bahor» uchun bu 50 + 20 = 70. Demak, 70 gacha tekshirish yetarli — biz 500 gacha tekshirdik. Bunday tizimlar kanonik deyiladi: ularda greedy doim to'g'ri.

Tekshirib ko'ring: Tangalar 1, 5 va 6 so'mlik. 10 so'mni greedy nechta tanga bilan beradi? Eng kami nechta?

3. Greedy qachon to'g'ri?

3.1 Ikki shart

Greedy to'g'ri ishlashi uchun masalada ikki xususiyat bo'lishi kerak:

1. Greedy tanlov xususiyati. Hozirgi eng yaxshi tanlov hech qachon "yo'lni yopib qo'ymaydi": eng yaxshi yechimlardan kamida bittasi aynan shu tanlov bilan boshlanadi.
2. Optimal quyi tuzilma. Tanlov qilingach, qolgan masala — xuddi shu turdagi kichikroq masala va uning eng yaxshi yechimi butun yechimning qismi bo'ladi.

Ikkinchi shartni DP darslaridan bilasiz — DP ham shunga tayanadi. Farq birinchisida. DP har qadamda hamma tanlovni sinaydi va eng yaxshisini jadvaldan oladi. Greedy esa bitta tanlov qiladi va boshqalariga qaramaydi. Shuning uchun greedy tezroq, lekin kamroq masalada to'g'ri.

3.2 Almashtirish dalili

Greedy to'g'riligini ko'rsatishning keng tarqalgan usuli — almashtirish dalili (exchange argument). Uning g'oyasi: "Faraz qilaylik, eng yaxshi yechim boshqa tanlov bilan boshlangan. Uning shu qismini greedy tanlovga almashtiramiz — yechim yomonlashmaydi. Demak, greedy tanlov bilan ham eng yaxshi yechim bor".

Kassa misolida: qaytimda 2 ta 10 000 lik bor deylik. Ularni bitta 20 000 likka almashtirsak, kupyuralar soni kamayadi. Shunday almashtirishlar «Bahor» kupyuralarida doim mumkin. {4, 3, 1} da esa 3 + 3 ni 4 + ... ga almashtirib bo'lmaydi — dalil buziladi va qarshi misol paydo bo'ladi.

Intervyuda yoki ishda to'liq isbot yozish kamdan-kam talab qilinadi. Lekin bitta savolni har doim bering: "Shu tanlovni boshqasiga almashtirsam, yomonlashishi mumkinmi?" Agar mumkin bo'lsa — greedy shubhali, DP ga o'ting.

3.3 Greedy va DP yonma-yon

Amaliy qoida: avval greedy g'oyasini sinab ko'ring va uni sodda yechim bilan solishtiring. Qarshi misol topilsa — DP. Topilmasa — sababini almashtirish dalili bilan tushuntirishga urinib ko'ring.

4. Jump game: zaryadlash nuqtalari

4.1 Masala

«Bahor» kuryeri elektroskuterda yuradi. Marshrutda zaryadlash nuqtalari ketma-ket turibdi. range[i] — i-nuqtada zaryad olsa, u yerdan necha nuqta oldinga yeta oladi. 0 — nuqta ishlamayapti. Kuryer 0-nuqtadan boshlaydi. Savol: oxirgi nuqtaga yetib bora oladimi?

Bu masala dasturchilar orasida jump game nomi bilan mashhur (LeetCode, 55-masala).

4.2 Sodda yechim: DP

Har nuqta uchun "bu yerga yetib bo'ladimi?" degan jadval tuzamiz. i-nuqtaga yetib bo'ladi, agar undan oldingi biror j-nuqtaga yetib bo'lsa va j dan i gacha zaryad yetsa:

function canReachSlow(range) {
  const ok = Array(range.length).fill(false);
  ok[0] = true; // boshlanish
  for (let i = 1; i < range.length; i++) {
    for (let j = 0; j < i; j++) {
      if (ok[j] && j + range[j] >= i) {
        ok[i] = true;
        break;
      }
    }
  }
  return ok[range.length - 1];
}

console.log(canReachSlow([2, 3, 1, 0, 2, 0, 1])); // true
console.log(canReachSlow([3, 2, 1, 0, 4])); // false

Ikki ichma-ich sikl — O(n²). Ikkinchi misolda hamma yo'l 3-nuqtaga olib keladi, u esa ishlamaydi.

4.3 G'oya: eng uzoq nuqtani eslab borish

Greedy savol beradi: "Hozircha eng uzoq qayergacha yeta olaman?" Nuqtalarni chapdan o'ngga yuramiz va bitta sonni yangilaymiz — farthest. Agar biror nuqta farthest dan nariroq bo'lsa, unga yetib bo'lmaydi — javob false. Aks holda shu nuqtadan qayergacha yetishni hisoblab, farthest ni kattalashtiramiz:

Nega bu to'g'ri? farthest gacha bo'lgan hamma nuqtaga yetib bo'ladi. Kuryer qisqaroq sakrab, oraliqdagi istalgan nuqtada to'xtay oladi. Shuning uchun aniq qaysi nuqtalarda to'xtashni eslab qolish shart emas — faqat chegarani bilish yetadi. Bu greedy ning invarianti: har qadamda rost bo'lib qoladigan haqiqat (Chegaraviy holatlar, brute force va invariant).

4.4 O'lchov

Greedy — bitta sikl, O(n) vaqt va O(1) xotira. DP — O(n²) vaqt va O(n) xotira. Benchmarking darsidagi usulda o'lchadik (har n alohida jarayonda, isitish, mediana; kirish urug'li generatordan, har nuqtada 1–3; raqamlar taxminiy):

DP da n ikki baravar oshganda vaqt to'rt baravar oshdi — kvadratik. Greedy esa bu o'lchamlarda mikrosekundlar oldi, nisbatni o'lchash uchun juda tez. Uni millionlab nuqtada o'lchadik:

Nisbat ×2,1, ×1,9, ×2,0 — chiziqli. Taqqoslang: 16 000 nuqtada DP 226 ms oldi. Greedy esa 8 million nuqtani 57 ms da ko'rib chiqdi.

5. Gas station: halqa marshrut

5.1 Masala

Kechqurun kuryer halqa bo'ylab 5 ta manzilga boradi va oxirida yana birinchisiga qaytadi. Har manzilda skuterni zaryadlaydi: charge[i] km lik zaryad oladi. i-manzildan keyingisigacha cost[i] km yo'l. Batareya boshida bo'sh. Qaysi manzildan boshlasa, halqani to'liq aylana oladi? Bunday manzil bo'lmasa — -1.

Bu klassik masala gas station (yoqilg'i shoxobchasi, LeetCode 134) deb ataladi.

5.2 Sodda yechim va greedy

Sodda yechim har manzildan boshlab ko'radi — O(n²). Greedy esa bitta o'tishda topadi:

function findStartSlow(charge, cost) {
  const n = charge.length;
  for (let start = 0; start < n; start++) {
    let battery = 0;
    let ok = true;
    for (let k = 0; k < n; k++) {
      const i = (start + k) % n; // halqa: oxiridan keyin boshi
      battery += charge[i] - cost[i];
      if (battery < 0) { ok = false; break; }
    }
    if (ok) return start;
  }
  return -1;
}

function findStart(charge, cost) {
  let total = 0; // butun halqa bo'yicha balans
  let battery = 0; // joriy boshlanishdan beri
  let start = 0;
  for (let i = 0; i < charge.length; i++) {
    const diff = charge[i] - cost[i];
    total += diff;
    battery += diff;
    if (battery < 0) { // start..i orasidan boshlab bo'lmaydi
      start = i + 1;
      battery = 0;
    }
  }
  return total < 0 ? -1 : start;
}

const charge = [3, 1, 2, 5, 4]; // har manzilda olinadigan km
const cost = [4, 3, 1, 2, 3]; // keyingi manzilgacha km
console.log(findStartSlow(charge, cost), findStart(charge, cost));
console.log(findStart([1, 2], [2, 2])); // -1

Konsolda:

2 2
-1

(start + k) % n — qoldiq operatori halqani yasaydi: 4-manzildan keyin yana 0-manzil keladi.

5.3 Nega greedy to'g'ri?

Ikki kuzatuv bor:

1. Jami zaryad jami yo'ldan kam bo'lsa (total < 0), qayerdan boshlamang, halqa aylanmaydi. Bunda javob -1.
2. start dan yo'lga chiqib, i da batareya manfiy bo'lsa, start va i orasidagi istalgan manzildan boshlash ham foyda bermaydi. Sababi: kuryer o'sha manzilga musbat (yoki nol) zaryad bilan kelgan edi. Nol zaryad bilan boshlasa, ahvoli faqat yomonroq bo'ladi. Shuning uchun keyingi nomzod — i + 1.

Bu ikki kuzatuv — almashtirish dalilining bir ko'rinishi. Natija: bitta sikl, O(n) vaqt, O(1) xotira. Sodda yechim esa O(n²).

Tekshirib ko'ring: charge = [2, 2, 2], cost = [3, 1, 2]. findStart nechani qaytaradi?

6. Huffman g'oyasi: ko'p uchraganga qisqa kod

6.1 Muammo

«Bahor» buyurtmalarini SMS orqali yuboradi va har bit pul turadi. Kompyuter har belgini odatda 8 bit (bitta bayt) bilan saqlaydi. Lekin buyurtmalarda ba'zi harflar juda ko'p uchraydi. Agar ko'p uchraydigan harfga qisqa kod, kam uchraydiganiga uzunroq kod bersak, umumiy uzunlik qisqaradi.

Huffman kodlash shuni greedy bilan qiladi. Uni 1952-yilda talaba David Huffman taklif qilgan. G'oya: har qadamda ikki eng kam uchraydigan belgini (yoki guruhni) birlashtirib, bitta tugun yasash. Birlashtirish daraxt hosil qiladi: chap shox — 0, o'ng shox — 1. Ildizdan bargacha yo'l — belgining kodi.

6.2 Daraxtni kuzatamiz

Matn: osh osh non. Pastda — hozirgi tugunlar ro'yxati (navbat), yuqorida — o'sib borayotgan daraxt. Har tugundagi son — necha marta uchrashi:

Natija: 26 bit. Odatdagi 8 bitli kodlashda 11 belgi — 88 bit. Hatto 5 xil belgi uchun eng qisqa teng uzunlikli kod (3 bit) ham 33 bit beradi. Kodlar bir-birining boshlanishi emas: 10 (o) hech bir boshqa kodning boshi emas. Shuning uchun bitlar ketma-ketligini ajratgichsiz o'qish mumkin.

6.3 Murakkablik

Kodimiz har qadamda ro'yxatni saralaydi: k xil belgi uchun O(k² log k). Bu yerda k = 5 — farqi yo'q. Lekin "har safar eng kichik ikkitasini ol" — bu Heap ning ishi. Heap bilan Huffman O(k log k) bo'ladi — real kutubxonalar shunday qiladi.

Huffman greedy si isbotlangan: belgilar alohida kodlansa, undan qisqa kod yo'q. Bu g'oya bugun ham gzip va PNG ichidagi DEFLATE formatida ishlaydi.

7. Chegaraviy holatlar

• Bitta nuqta. canReach([0]) — true: kuryer allaqachon oxirgi nuqtada. findStart([5], [3]) — 0.
• Nol qaytim. makeChange(0) — [], xato emas.
• Qaytarib bo'lmaydigan summa. makeChange(1500) — null. Javobni null bilan tekshirmasdan ishlatsangiz, .length da TypeError chiqadi.
• Teng chastotalar. Huffman'da tenglik bo'lsa, daraxt shakli tartibga bog'liq. Kodlar boshqacha chiqishi mumkin, lekin umumiy bitlar soni bir xil. Testda kodlarning o'zini emas, jami bitlarni tekshiring.
• Bitta xil belgi. huffmanCodes("aaa") — daraxtda bitta barg, yo'l bo'sh. Shuning uchun kodda code || "0" bor: belgi baribir 1 bitli kod oladi.

8. Ko'p uchraydigan xatolar

8.1 Greedy ni tekshirmasdan ishonish

Uchta misolda to'g'ri chiqdi — demak to'g'ri? Yo'q. {4, 3, 1} da 1 dan 5 gacha hamma summa to'g'ri, faqat 6 da xato. Tuzatish: sodda (yoki DP) yechim bilan yuzlab kirishda solishtiring. Buning to'liq usulini Chegaraviy holatlar va algoritmni testlash darsida o'rganamiz.

8.2 Kupyuralarni saralamaslik

makeChange kupyuralar kattadan kichikka berilganiga tayanadi. [1000, 5000, ...] bersangiz, hamma qaytim mingliklarda chiqadi. Tuzatish: funksiya ichida toSorted((a, b) => b - a) qiling yoki tartibni izohda talab qiling.

8.3 Noto'g'ri mezon bo'yicha ochko'zlik

Knapsack'da "eng yuqori baholi taom" yoki "eng arzon taom" bo'yicha greedy — ikkalasi ham adashadi. "Baho ÷ narx" bo'yicha greedy ko'pincha yaxshi, lekin u ham kafolat bermaydi. Taomni bo'lib bo'lmaydi: yarim osh sotilmaydi. Taomni bo'lsa bo'ladigan variantda ("kasr knapsack") esa "baho ÷ narx" greedy aniq to'g'ri. Tuzatish: mezonni tanlagach, qarshi misol qidiring.

8.4 Halqani unutish

Gas station'da sodda yechimda % n siz yozsangiz, indeks massivdan chiqib undefined bo'ladi. undefined - 3 — NaN, NaN < 0 esa false. Natijada xato jim o'tib ketadi. Tuzatish: halqa masalalarida indeksni doim % n bilan oling va oxirgi manzildan boshlanadigan holatni test qiling.

9. Mashqlar

1-mashq (oson): Qaytimni sanang

«Bahor» kassasida qaytim 87 000 so'm. Greedy nechta kupyura beradi? Javob: [:5]. Endi {4, 3, 1} tangalarida 6 so'mni greedy bilan bering — tangalar soni: [:3].

2-mashq (o'rta): Eng kam to'xtash

Jump game'ning ikkinchi varianti: kuryer oxirgi nuqtaga albatta yetadi. Lekin har to'xtash vaqt oladi. Funksiya minStops(range) eng kam to'xtashlar sonini qaytarsin. Yetib bo'lmasa — -1. Ishora: ikki chegarani saqlang. Birinchisi — joriy zaryad yetadigan chegara, ikkinchisi — keyingi to'xtash bilan eng uzoq nuqta. Joriy chegaraga yetganda to'xtash shart.

function minStops(range) {
  let stops = 0;
  let currentEnd = 0; // joriy zaryad yetadigan chegara
  let farthest = 0; // keyingi to'xtash bilan eng uzoq nuqta
  for (let i = 0; i < range.length - 1; i++) {
    farthest = Math.max(farthest, i + range[i]);
    if (i === currentEnd) { // zaryad tugadi — to'xtash kerak
      if (farthest <= i) return -1; // oldinga yurib bo'lmaydi
      stops++;
      currentEnd = farthest;
    }
  }
  return stops;
}

console.log(minStops([2, 3, 1, 1, 4])); // 2
console.log(minStops([1])); // 0
console.log(minStops([3, 2, 1, 0, 4])); // -1

3-mashq (qiyin): Kupyura tizimini tekshiruvchi test

kurs/mashqlar/14/54-greedy/qaytim.test.mjs faylida findCounterexample(coins) yozing. U Kozen–Zaks chegarasigacha (ikki eng katta tanga yig'indisi) tekshirsin. Tangalar kattadan kichikka berilgan va 1 albatta bor. Testlar:

1. «Bahor» kupyuralari (ming so'mda) — null.
2. {4, 3, 1} → 6, {10, 7, 1} → 14.
3. Qarshi misolda greedy haqiqatan ko'proq tanga beradi.
4. Chegaraviy: 0 so'm — 0 tanga; qaytarib bo'lmaydigan summa — Infinity.

// kurs/mashqlar/14/54-greedy/qaytim.test.mjs
import { test } from "node:test";
import assert from "node:assert/strict";

function greedyCount(amount, coins) {
  let count = 0;
  for (const coin of coins) {
    count += Math.floor(amount / coin);
    amount %= coin;
  }
  return amount === 0 ? count : Infinity;
}

function dpCount(amount, coins) {
  const best = Array(amount + 1).fill(Infinity);
  best[0] = 0;
  for (let a = 1; a <= amount; a++) {
    for (const coin of coins) {
      if (coin <= a) best[a] = Math.min(best[a], best[a - coin] + 1);
    }
  }
  return best[amount];
}

function findCounterexample(coins) {
  const limit = coins[0] + coins[1]; // Kozen–Zaks chegarasi
  for (let a = 1; a < limit; a++) {
    if (greedyCount(a, coins) !== dpCount(a, coins)) return a;
  }
  return null;
}

test("«Bahor» kupyuralari — greedy doim to'g'ri", () => {
  assert.equal(findCounterexample([50, 20, 10, 5, 2, 1]), null);
});

test("qarshi misollar: {4, 3, 1} → 6, {10, 7, 1} → 14", () => {
  assert.equal(findCounterexample([4, 3, 1]), 6);
  assert.equal(findCounterexample([10, 7, 1]), 14);
});

test("qarshi misolda greedy haqiqatan ko'proq tanga beradi", () => {
  assert.equal(greedyCount(6, [4, 3, 1]), 3); // 4 + 1 + 1
  assert.equal(dpCount(6, [4, 3, 1]), 2); // 3 + 3
});

test("chegaraviy: 0 so'm — 0 tanga, 1 yo'q — Infinity", () => {
  assert.equal(greedyCount(0, [5, 2]), 0);
  assert.equal(greedyCount(3, [5, 2]), Infinity);
  assert.equal(dpCount(3, [5, 2]), Infinity);
});

✔ «Bahor» kupyuralari — greedy doim to'g'ri (2.9409ms)
✔ qarshi misollar: {4, 3, 1} → 6, {10, 7, 1} → 14 (0.1543ms)
✔ qarshi misolda greedy haqiqatan ko'proq tanga beradi (0.1006ms)
✔ chegaraviy: 0 so'm — 0 tanga, 1 yo'q — Infinity (0.1ms)
ℹ tests 4
ℹ suites 0
ℹ pass 4
ℹ fail 0
ℹ cancelled 0
ℹ skipped 0
ℹ todo 0
ℹ duration_ms 8.6662

4-mashq: Amaliy tajriba — greedy qatorlari

kurs/mashqlar/14/MURAKKABLIK.md jadvaliga bugungi qatorlarni qo'shing: qaytim (greedy), tangalar (DP), jump game (DP va greedy), gas station (sodda va greedy), Huffman (saralash va heap bilan). Yangi ustun qo'shing: "Greedy to'g'rimi?" — ha, yo'q yoki "faqat kanonik tizimda".

| Masala | Yechim | Vaqt | Xotira | Greedy to'g'rimi? |
|---|---|---|---|---|
| Qaytim | greedy | O(k + javob) | O(javob) | faqat kanonik |
| Tangalar | DP | O(S · k) | O(S) | — |
| Jump game | DP | O(n²) | O(n) | — |
| Jump game | greedy | O(n) | O(1) | ha (invariant) |
| Gas station | har startdan | O(n²) | O(1) | — |
| Gas station | greedy | O(n) | O(1) | ha |
| Huffman | saralash | O(k² log k) | O(k) | ha (isbotlangan) |
| Huffman | heap | O(k log k) | O(k) | ha |

git add 14/MURAKKABLIK.md 14/54-greedy
git commit -m "14/54: greedy — qarshi misol testi, jump game, gas station"

10. Real ishda

• Siqish. gzip, PNG va HTTP javoblarini siqish (DEFLATE) Huffman kodlashdan foydalanadi. Brauzer har sahifa ochganda shu greedy natijasini qayta yoyadi.
• Rejalashtirish. Navbatdagi vazifalarni "eng tez tugaydigani birinchi" tartibida bajarish va bir xonaga eng ko'p uchrashuv sig'dirish — greedy. Buni keyingi darsda intervallarda ko'ramiz.
• Tarmoqlar. Eng qisqa yo'lni topadigan Dijkstra algoritmi (Eng qisqa yo'l) va minimal skelet daraxti (Union-Find va minimal skelet daraxti) — greedy algoritmlar.
• Taxminiy yechimlar. Kuryer yo'nalishi kabi og'ir masalalarda aniq javob juda qimmat. Shunda "eng yaqin manzilga bor" kabi greedy "yetarlicha yaxshi" javob beradi — Asosiy murakkablik sinflari darsidagi va'dani shu yerda yopamiz. Har qadamda qolgan manzillar ichidan eng yaqinini tanlash O(n²) ish: n! tartibni sinashdan beqiyos tez. Yo'l eng qisqasidan biroz uzunroq chiqishi mumkin — bu tezlik uchun ongli to'lov.
• Intervyu. "Jump Game", "Gas Station", "Coin Change" va "Assign Cookies" — greedy savollar. Intervyuer ko'pincha so'raydi: "Bu greedy nega to'g'ri?" Javob — almashtirish dalili yoki invariant.

Xulosa

• Greedy har qadamda hozirgi eng yaxshi tanlovni qiladi va unga qaytmaydi — tez, lekin har doim ham to'g'ri emas.
• Greedy noto'g'ri ekanini bitta qarshi misol ko'rsatadi: {4, 3, 1} da 6 so'm. Qarshi misolni DP bilan avtomatik qidiring.
• To'g'rilik uchun ikki shart: greedy tanlov xususiyati va optimal quyi tuzilma; tushuntirish usuli — almashtirish dalili yoki invariant.
• Jump game va gas station — bitta sikl, O(n). O'lchovda DP 16 000 nuqtada 226 ms oldi, greedy 8 million nuqtada 57 ms.
• Huffman: ikki eng kamini birlashtirish — ko'p uchraydiganga qisqa kod; heap bilan O(k log k).

Keyingi dars: Intervallar va sweep line — «Bahor» stol bronlari: kesishgan vaqtlarni birlashtirish, bir vaqtda nechta stol kerakligini topish va vaqt chizig'i bo'ylab "supurish".

Manbalar

• Thomas H. Cormen va boshq., "Introduction to Algorithms", 4-nashr, MIT Press, 2022 — 15-bob (greedy algoritmlar, Huffman kodlari).
• D. Kozen, S. Zaks, "Optimal bounds for the change-making problem", Theoretical Computer Science 123 (1994).
• D. A. Huffman, "A Method for the Construction of Minimum-Redundancy Codes", Proceedings of the IRE, 1952.
• LeetCode masalalari (shartlarini o'zingiz o'qing): 45 "Jump Game II", 55 "Jump Game", 134 "Gas Station", 322 "Coin Change".