Грокаємо алгоритми

Повне пояснення

Коротке пояснення

Бінарний пошук швидко знаходить позицію заданого елемента у відсортованому масиві, розділяючи його на половини. Кожен крок зменшує область пошуку вдвічі, поки не знайде елемент або не доведеться повернути «не знайдено».

Аналогія

Уявіть, що ви шукаєте слово у словнику: відкриваєте книгу посередині, читаєте перше слово і вирішуєте, чи слід шукати ліворуч (перші букви) або праворуч (далі в алфавіті).

Коли застосовувати

• Масив або список вже відсортований за зростанням/спаданням.
• Потрібна швидка точкова пошукова операція (O(log n)).
• Кількість запитів великі, а час на сортування не критичний.
• Пошук елемента в масиві, де індекси важливі (наприклад, у базах даних).

Кроки алгоритму

1. Визначити межі пошуку: low = 0, high = n‑1.
2. Якщо low > high – елемент не знайдено, завершити.
3. Обчислити середній індекс mid = Math.floor((low + high) / 2).
4. Якщо arr[mid] === target – повернути mid.
5. Якщо arr[mid] > target, встановити high = mid - 1 і повернутися до кроку 2.
6. Якщо arr[mid] < target, встановити low = mid + 1 і повернутися до кроку 2.

Візуальна інтуїція (текстова)

Масив: [1, 3, 5, 7, 9, 11]
Target: 7

1. low=0, high=5 → mid=2 (arr[2]=5) < 7 → low=3
2. low=3, high=5 → mid=4 (arr[4]=9) > 7 → high=3
3. low=3, high=3 → mid=3 (arr[3]=7) == 7 → знайдено

Складність

Часова складність: O(log n) у найкращому, середньому й гіршому випадках. Пам’ятна складність: O(1), бо використовуються лише кілька змінних.

Код (js)

// Бінарний пошук у відсортованому масиві
function binarySearch(arr, target) {
  // ініціалізуємо межі пошуку
  let low = 0;
  let high = arr.length - 1;

  // поки область пошуку не порожня
  while (low <= high) {
    // обчислюємо середній індекс
    const mid = Math.floor((low + high) / 2);

    // якщо знайдено, повертаємо індекс
    if (arr[mid] === target) {
      return mid;
    }

    // якщо елемент у середньому більший за ціль, шукаємо ліворуч
    if (arr[mid] > target) {
      high = mid - 1;
    } else { // інакше шукаємо праворуч
      low = mid + 1;
    }
  }

  // елемент не знайдено
  return null;
}

// Тестовий приклад
console.log(binarySearch([1, 3, 5, 7, 9], 7)); // очікуваний результат: 3
console.log(binarySearch([1, 3, 5, 7, 9], 2)); // очікуваний результат: null

Типові помилки і поради

1. Не сортувати масив: алгоритм працює лише з упорядкованими даними. Переконайтеся, що масив відсортований.
2. Використання mid = (low + high) / 2 без округлення: у великих масивах може виникнути переповнення. Завжди використовуйте Math.floor.
3. Забудьте про інкремент/декремент: після зміни low або high потрібно повернутися до циклу, інакше цикл може застрягти.
4. Повернення -1 замість null: це залежить від контексту, але null чітко сигналізує про «не знайдено».
5. Оптимізація: для дуже великих масивів можна використовувати рекурсію, але це збільшує використання стеку.

Перевір себе

1. Яка складність бінарного пошуку у найгіршому випадку?
2. Чому важливо, щоб масив був відсортований перед пошуком?

Повне пояснення

Коротке пояснення

Алгоритм Крускала шукає мінімальне остовне дерево, вибираючи ребра з найменшою вагою без створення циклів.

Аналогія

Уявіть, що ви хочете з’єднати міста дорогами так, щоб витрати були мінімальними і не було замкнутих циклів; Крускал вибирає найдешевші дороги, поки не з’єднав усі міста.

Коли застосовувати

• Зважений граф з незв’язаними вершинами.
• Потрібно мінімізувати суму ваг у з’єднанні всіх вершин.
• Граф не має зайвих циклів у кінцевому результаті.
• Кількість ребер достатня для побудови дерева (|E| ≥ |V|-1).
• Потрібна швидка реалізація без складних структурування даних.

Кроки алгоритму

1. Сортувати усі ребра за зростанням ваги.
2. Ініціалізувати кожну вершину як окремий компонент (Union‑Find).
3. Проходити по відсортованих ребрах.
4. Якщо вершини ребра належать різним компонентам, додати ребро до дерева і об’єднати компоненти.
5. Продовжувати, доки не буде |V|-1 ребер у дереві.

Візуальна інтуїція (текстова)

Вершини: A B C D
Ребра (вага): AB(1), AC(3), AD(4), BC(2), CD(5)

Сортування: AB, BC, AC, AD, CD

Крок 1: AB → додаємо (A,B)
Крок 2: BC → додаємо (B,C) – A,B,C у одному компоненті
Крок 3: AC → пропускаємо (цикл)
Крок 4: AD → додаємо (A,D) – всі вершини з’єднані
Результат: дерево зі сторонами AB, BC, AD (сумарна вага 1+2+4=7)

Складність

• Час: O(E log E) через сортування ребер; Union‑Find з path compression дає O(E α(V)).
• Пам’ять: O(V+E) для зберігання графу, списку ребер і структури Union‑Find.

Код (js)

// Клас для структури Union‑Find (Disjoint Set Union)
class DSU {
  constructor(n) {
    this.parent = Array.from({ length: n }, (_, i) => i); // ініціалізуємо кожну вершину як власний батько
    this.rank = Array(n).fill(0); // ранг для оптимізації об’єднання
  }

  find(x) {
    // рекурсивний пошук батька з path compression
    if (this.parent[x] !== x) {
      this.parent[x] = this.find(this.parent[x]); // зменшуємо шлях
    }
    return this.parent[x];
  }

  union(x, y) {
    const rootX = this.find(x);
    const rootY = this.find(y);
    if (rootX === rootY) return false; // вже в одному компоненті
    // об’єднуємо за рангом
    if (this.rank[rootX] < this.rank[rootY]) {
      this.parent[rootX] = rootY;
    } else if (this.rank[rootX] > this.rank[rootY]) {
      this.parent[rootY] = rootX;
    } else {
      this.parent[rootY] = rootX;
      this.rank[rootX] += 1;
    }
    return true; // об’єднання успішне
  }
}

// Функція Крускала: приймає кількість вершин і масив ребер [u, v, weight]
function kruskal(numVertices, edges) {
  // Крок 1: сортування ребер за вагою
  edges.sort((a, b) => a[2] - b[2]);

  const dsu = new DSU(numVertices);
  const mst = []; // мінімальне остовне дерево
  let totalWeight = 0;

  // Крок 2: перебір відсортованих ребер
  for (const [u, v, w] of edges) {
    if (dsu.union(u, v)) { // якщо вершини в різних компонентах
      mst.push([u, v, w]); // додаємо ребро до MST
      totalWeight += w;
    }
  }

  return { mst, totalWeight };
}

// Тестовий приклад
const vertices = 4; // A=0, B=1, C=2, D=3
const edges = [
  [0, 1, 1], // AB
  [0, 2, 3], // AC
  [0, 3, 4], // AD
  [1, 2, 2], // BC
  [2, 3, 5]  // CD
];
const result = kruskal(vertices, edges);
console.log(result.mst); // очікуваний результат: [[0,1,1],[1,2,2],[0,3,4]]
console.log(result.totalWeight); // очікуваний результат: 7

Типові помилки і поради

1. Не сортувати ребра – алгоритм працює лише з відсортованим списком.
2. Використовувати звичайний масив замість Union‑Find – це призведе до O(V E) часу.
3. Забути про цикли – без Union‑Find можна випадково додати ребро, що створює цикл.
4. Неправильний індекс вершини – у JS масиви починаються з 0, тому переконайтеся, що вершини позначені відповідно.
5. Не обробляти випадок, коли граф роз’єднаний – алгоритм поверне часткове дерево; перевірте, чи кількість ребер = V‑1.

Перевір себе

1. Яка складність сортування ребер у Крускалі?
2. Для чого потрібен Union‑Find у цьому алгоритмі?

Повне пояснення

Коротке пояснення

Задача про рюкзак шукає найцінніший набір предметів, що вміщуються у рюкзак заданої ваги. Алгоритм використовує динамічне програмування, щоб уникнути повторного обчислення тих самих підзадач.

Аналогія

Уявіть, що ви йдете в магазин і маєте обмежений кошик. Ви розглядаєте кожен товар: чи варто його взяти, щоб отримати максимальну користь, не перевищуючи обмеження кошика.

Коли застосовувати

• Задача з обмеженою вагою рюкзака (0/1).
• Вхід: масив предметів з вагою та цінністю.
• Очікуваний результат: максимальна сумарна цінність, що не перевищує вагу.
• Підходить для невеликих до середніх розмірів (до кількох тисяч предметів).
• Не підходить, коли ваги дуже великі (пам’ять стає проблемою).

Кроки алгоритму

1. Створити двовимірну таблицю dp, де dp[i][w] – максимальна цінність з перших i предметів при вазі w.
2. Ініціалізувати dp[0][*] = 0 (без предметів – нульова цінність).
3. Для кожного предмету i від 1 до n:
   • Для кожної ваги w від 0 до W:
     • Якщо вага предмету > w, копіювати dp[i-1][w].
     • Інакше обрати максимум між dp[i-1][w] і dp[i-1][w - weight_i] + value_i.
4. Повернути dp[n][W].

Візуальна інтуїція (текстова)

Вага W = 5
Предмети: [{w:2,v:3},{w:3,v:4}]

dp[0] = [0,0,0,0,0,0]
dp[1] = [0,0,3,3,3,3]
dp[2] = [0,0,3,4,7,7]

Результат: 7 (обидва предмети)

Складність

• Час: O(n·W), де n – кількість предметів, W – максимальна вага рюкзака.
• Пам’ять: O(n·W) для повної таблиці, або O(W) при оптимізації одновимірним масивом.
• Найгірший випадок: коли всі предмети мають вагу 1, що збільшує розмір таблиці.

Код (js)

// Функція, що обчислює максимальну цінність рюкзака
function knapsack(items, maxWeight) {
  // items – масив об’єктів {weight, value}
  const n = items.length;
  // Створюємо двовимірну таблицю dp (n+1) x (maxWeight+1)
  const dp = Array.from({ length: n + 1 }, () => Array(maxWeight + 1).fill(0));

  // Проходимо по кожному предмету
  for (let i = 1; i <= n; i++) {
    const { weight, value } = items[i - 1]; // поточний предмет
    for (let w = 0; w <= maxWeight; w++) {
      if (weight > w) {
        // Якщо предмет важчий за поточну вагу, не можемо взяти його
        dp[i][w] = dp[i - 1][w];
      } else {
        // Вибираємо максимум між не взятим і взяттям предмету
        const without = dp[i - 1][w];
        const withItem = dp[i - 1][w - weight] + value;
        dp[i][w] = Math.max(without, withItem);
      }
    }
  }

  // Повертаємо максимальну цінність для повної ваги
  return dp[n][maxWeight];
}

// Тестовий приклад
const items = [
  { weight: 2, value: 3 },
  { weight: 3, value: 4 },
  { weight: 4, value: 8 }
];
console.log(knapsack(items, 5)); // очікуваний результат: 7

Типові помилки і поради

1. Використання неправильного індексу – пам’ятайте, що масив items починається з 0, а таблиця dp – з 1.
2. Неправильне порівняння ваги – перевірка weight > w повинна бути перед обчисленням максимуму.
3. Забудьте про 0‑ваговий рядок – без предметів цінність нульова, тому ініціалізація dp[0][*] = 0 критична.
4. Пам’ять – для великих W використовуйте одновимірний масив, оновлюючи з кінця до початку.
5. Оптимізація – можна обчислювати dp лише для ваг, що досяжні (наприклад, сумарна вага всіх предметів), щоб зменшити розмір таблиці.

Перевір себе

1. Яка складність часу для n предметів і максимальної ваги W?
2. Що робить рядок dp[i][w] = Math.max(without, withItem);?

Повне пояснення

Коротке пояснення

Алгоритм Дейкстри шукає найкоротший шлях від однієї вершини до всіх інших у графі з невід’ємними вагами, використовуючи пріоритетну чергу для вибору вершини з найменшою відомою довжиною.

Аналогія

Уявіть, що ви плануєте подорож по місту: кожен вузол – це пункт, а ваги – це час проїзду. Алгоритм спочатку вибирає найкоротший шлях до найближчого пункту, потім розширює маршрут, додаючи нові найкоротші шляхи.

Коли застосовувати

• Знайти найкоротший шлях у графі з невід’ємними вагами.
• Потрібно обчислити відстані до всіх вершин з однієї точки.
• Граф не містить циклів із негативними вагами.
• Вхідний граф представлений у вигляді списку суміжності або матриці.
• Потрібна ефективність для великих графів з десятками тисяч вершин.

Кроки алгоритму

1. Ініціалізувати відстані: source = 0, інші – нескінченність.
2. Додати усі вершини до пріоритетної черги з їхніми відстанями.
3. Витягнути вершину з найменшою відстанню (current).
4. Для кожного сусіда current: обчислити нову відстань через current.
5. Якщо нова відстань менша, оновити її і додати сусіда в чергу.
6. Повторювати кроки 3–5, доки черга не порожня.

Візуальна інтуїція (текстова)

Вершини: A, B, C
Відстані: [A=0, B=∞, C=∞]
Черга: (A,0)

Витяг A → B (2), C (5) → оновити: [A=0, B=2, C=5]
Черга: (B,2), (C,5)

Витяг B → C (1) → нова: 2+1=3 <5 → оновити C
Черга: (C,3)

Складність

Часова складність: O((V+E) log V), де V – кількість вершин, E – ребер, завдяки пріоритетній черзі. Пам’ятна складність: O(V+E) для зберігання графу та відстаней.

Код (js)

// Алгоритм Дейкстри для графу, представленного списком суміжності
function dijkstra(graph, start) {
  // Ініціалізуємо відстані: до всіх вершин – нескінченність
  const distances = {};
  for (const vertex in graph) {
    distances[vertex] = Infinity; // ініціалізація
  }
  distances[start] = 0; // стартова вершина має довжину 0

  // Пріоритетна черга (міні-heap) – реалізована як масив з простим пошуком
  const priorityQueue = [];
  function enqueue(vertex, priority) {
    priorityQueue.push({ vertex, priority });
    // Сортуємо за зростанням пріоритету (мінімальна відстань на початку)
    priorityQueue.sort((a, b) => a.priority - b.priority);
  }

  enqueue(start, 0); // додаємо стартову вершину

  while (priorityQueue.length > 0) {
    // Витягуємо вершину з найменшою відстанню
    const { vertex: currentVertex, priority: currentDistance } = priorityQueue.shift();

    // Якщо знайдено новішу (меншу) відстань, пропускаємо
    if (currentDistance > distances[currentVertex]) continue;

    // Перебираємо сусідів поточної вершини
    const neighbors = graph[currentVertex];
    for (const neighbor of neighbors) {
      const { vertex: nextVertex, weight } = neighbor;
      const newDistance = distances[currentVertex] + weight; // нова відстань через current
      if (newDistance < distances[nextVertex]) {
        // Оновлюємо відстань і додаємо в чергу
        distances[nextVertex] = newDistance;
        enqueue(nextVertex, newDistance);
      }
    }
  }

  return distances; // повертаємо таблицю мінімальних довжин
}

// Тестовий приклад
const graph = {
  A: [{ vertex: 'B', weight: 2 }, { vertex: 'C', weight: 5 }],
  B: [{ vertex: 'A', weight: 2 }, { vertex: 'C', weight: 1 }],
  C: [{ vertex: 'A', weight: 5 }, { vertex: 'B', weight: 1 }],
};
console.log(dijkstra(graph, 'A')); // очікуваний результат: { A: 0, B: 2, C: 3 }

Типові помилки і поради

1. Використання масиву як черги без сортування – призводить до O(V^2) часу. Використайте heap або бібліотеку.
2. Забудьте оновити відстань у черзі – нові значення не будуть враховані. Завжди додавайте вершину після оновлення.
3. Невірне оброблення графу з циклом – алгоритм працює лише для невід’ємних ваг. Перевірте дані перед запуском.
4. Не ініціалізувати відстань до всіх вершин – залишить undefined, що призведе до NaN.
5. Оптимізація – використайте Set для відстеження оброблених вершин, щоб уникнути зайвих ітерацій.

Перевір себе

1. Яка складність алгоритму Дейкстри при використанні міні-heap?
2. Чому граф не повинен містити негативних ваг для правильного виконання алгоритму?

Повне пояснення

Коротке пояснення

Merge Sort розбиває масив на дві частини, сортує кожну рекурсивно і потім об’єднує їх у один відсортований масив. Ідея полягає в тому, що об’єднання двох вже відсортованих списків можна виконати за лінійний час.

Аналогія

Уявіть, що ви маєте два купи книг, кожна вже упорядкована за розміром. Щоб отримати одну купу, ви берете найменшу книгу з кожної купи і кладете її в новий список, продовжуючи до тих пір, поки обидві купи не порожні.

Коли застосовувати

• Масив великий, і потрібна гарантована O(n log n) складність.
• Потрібно стабільне сортування (зберігає порядок однакових елементів).
• Пам’ять достатня для додаткового простору O(n).
• Дані не піддаються швидкому вставленню/видаленню, як у бінарному дереві.

Кроки алгоритму

1. Якщо масив має 0 або 1 елемент, повернути його.
2. Знайти середину масиву і розділити на ліву та праву частини.
3. Рекурсивно викликати Merge Sort для кожної половини.
4. Об’єднати дві відсортовані частини у один масив, порівнюючи їх елементи.
5. Повернути об’єднаний масив.

Візуальна інтуїція (текстова)

[4, 1, 3, 2]
├─ розділити → [4, 1] | [3, 2]
│   ├─ розділити → [4] | [1]
│   │   → повернути [1, 4]
│   ├─ розділити → [3] | [2]
│   │   → повернути [2, 3]
│   └─ об’єднати → [1, 4] + [2, 3] = [1, 2, 3, 4]
└─ повернути

Складність

Часова складність: O(n log n) у найгіршому, середньому й кращому випадках. Пам’ятна складність: O(n) через тимчасовий масив під час злиття.

Код (js)

// Merge Sort: рекурсивне розділення і злиття
function mergeSort(array) {
  // Якщо масив має 0 або 1 елемент, він вже відсортований
  if (array.length <= 1) {
    return array;
  }

  // Знаходимо середину масиву для розділення
  const middle = Math.floor(array.length / 2);
  const leftHalf = array.slice(0, middle); // лівий підмасив
  const rightHalf = array.slice(middle);   // правий підмасив

  // Рекурсивно сортуємо обидві половини
  const sortedLeft = mergeSort(leftHalf);
  const sortedRight = mergeSort(rightHalf);

  // Об’єднуємо відсортовані половини
  return merge(sortedLeft, sortedRight);
}

// Функція злиття двох відсортованих масивів
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]);
      i++;
    } else {
      result.push(right[j]);
      j++;
    }
  }

  // Якщо залишилися елементи в лівому масиві, додаємо їх
  while (i < left.length) {
    result.push(left[i]);
    i++;
  }

  // Якщо залишилися елементи в правому масиві, додаємо їх
  while (j < right.length) {
    result.push(right[j]);
    j++;
  }

  return result; // повертаємо об’єднаний масив
}

// Тестовий приклад
console.log(mergeSort([4, 1, 3, 2])); // очікуваний результат: [1, 2, 3, 4]

Типові помилки і поради

1. Використання slice без копіювання – slice створює новий масив, тому пам’ять збільшується. Якщо потрібна ін‑плейс оптимізація, використовуйте індекси.
2. Неправильне обчислення середини – Math.floor(array.length / 2) гарантує, що масив розділяється рівномірно.
3. Забуття об’єднання – без функції merge рекурсія не поверне відсортований результат.
4. Перевантаження стеку – для дуже великих масивів можна замінити рекурсію на ітеративний підхід.
5. Нестабільність – Merge Sort стабільний, тому однакові елементи зберігають порядок.

Перевір себе

1. Яка складність Merge Sort у найгіршому випадку?
2. Чому алгоритм стабільний, а Quick Sort ні за замовчуванням?

Повне пояснення

Коротке пояснення

DFS (Depth‑First Search) просувається глибоко по графу, відвідуючи вершину і рекурсивно переходячи до її суміжних. BFS (Breadth‑First Search) розширює рівень за рівнем, використовуючи чергу, і таким чином знаходить найкоротший шлях у неважкості.

Аналогія

DFS – це, як розкопування підземелля: ви йдете глибоко в одну галю, не повертаючись, доки не дійдете до кінця. BFS – це пошук у лабіринті, коли ви розглядаєте всі двері першого рівня, потім всіх дверей другого і так далі.

Коли застосовувати

• Потрібно знайти будь‑який шлях між двома вершинами.
• Граф не має ваг, а важливий лише порядок обходу.
• Потрібно перевірити зв’язність графа.
• Пошук у глибину підходить для задач, де потрібен повний список всіх шляхів.
• BFS використовується, коли треба знайти найкоротший шлях у неважкості.

Кроки алгоритму

1. Відкрити вершину, позначити її як відвідану.
2. Для DFS: рекурсивно або з стеком обробити кожну суміжну вершину, що ще не відвідана.
3. Для BFS: додати суміжні вершини до черги, позначити їх як відвідані.
4. Повторювати крок 2/3, доки не буде оброблено всі вершини.
5. Повернути список відвіданих вершин або шлях, якщо потрібен.

Візуальна інтуїція (текстова)

DFS:

A → B → D
    ↘ E
C → F

BFS:

Level 0: A
Level 1: B, C
Level 2: D, E, F

Складність

DFS і BFS мають O(V + E) час, де V – кількість вершин, E – ребер. Пам’ять: DFS рекурсивно потребує O(V) стеку, BFS – O(V) черги. У найгіршому випадку обидва обходять усі вершини і ребра.

Код (js)

// Граф представляється у вигляді об’єкта: ключ – вершина, значення – масив суміжних вершин
const graph = {
  A: ['B', 'C'],
  B: ['A', 'D', 'E'],
  C: ['A', 'F'],
  D: ['B'],
  E: ['B', 'F'],
  F: ['C', 'E']
};

// ---------- DFS (рекурсивний) ----------
function dfs(start, visited = new Set(), order = []) {
  // 1. Позначаємо поточну вершину як відвідану
  visited.add(start);
  order.push(start); // 2. Додаємо до порядку обходу

  // 3. Рекурсивно обходимо суміжні вершини, що ще не відвідані
  for (const neighbor of graph[start]) {
    if (!visited.has(neighbor)) {
      dfs(neighbor, visited, order);
    }
  }

  return order; // 4. Повертаємо повний порядок обходу
}

// ---------- BFS (черговий) ----------
function bfs(start) {
  const visited = new Set(); // 1. Створюємо множину відвіданих
  const queue = [start];     // 2. Черга з початковою вершиною
  const order = [];          // 3. Порядок обходу

  visited.add(start);

  while (queue.length > 0) {
    const vertex = queue.shift(); // 4. Витягуємо з черги
    order.push(vertex);           // 5. Додаємо до порядку

    for (const neighbor of graph[vertex]) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor); // 6. Позначаємо як відвідану
        queue.push(neighbor);   // 7. Додаємо до черги
      }
    }
  }

  return order; // 8. Повертаємо порядок обходу
}

// ---------- Тестові приклади ----------
console.log(dfs('A')); // очікуваний результат: ['A', 'B', 'D', 'E', 'F', 'C']
console.log(bfs('A')); // очікуваний результат: ['A', 'B', 'C', 'D', 'E', 'F']

Типові помилки і поради

1. Не позначати вершину як відвідану перед рекурсивним викликом – це призведе до зациклення.
2. Використовувати глобальну змінну для visited у рекурсії – це зіпсує результати при кількох викликах.
3. Забувати очищати чергу у BFS – залишиться зайва пам’ять і неправильний порядок.
4. Не перевіряти, чи вершина існує у графі – це викличе помилку.
5. Використовувати стек замість черги у BFS – алгоритм перестане працювати як ширинний.

Перевір себе

1. Яка складність часу має DFS у найгіршому випадку?
2. Чому BFS гарантує знайти найкоротший шлях у неважкості?

Повне пояснення

Коротке пояснення

Алгоритм Хаффмана генерує коди для символів, використовуючи бінарне дерево: частіші символи отримують короткі коди, рідкісні — довгі. Це дозволяє зменшити загальну кількість бітів, необхідних для представлення тексту.

Аналогія

Уявіть, що ви створюєте інструкції для пошуку предметів у бібліотеці: найпопулярніші книги отримують короткі, прості позначки (наприклад, «A»), а рідкісні — довші послідовності (наприклад, «ABCD»). Це економить місце на полицях.

Коли застосовувати

• При стисненні тексту, де частоти символів різняться (наприклад, англійський текст).
• Коли потрібна швидка декодування без додаткових метаданих.
• У системах, де обмежений простір пам’яті (мобільні пристрої).
• У форматах файлів, що підтримують власний код (наприклад, JPEG).
• Коли важлива швидкість передачі даних.

Кроки алгоритму

1. Підрахувати частоти кожного символу у вхідному тексті.
2. Створити пріоритетну чергу (min‑heap) з вузлів, кожен з яких містить символ і його частоту.
3. Повторно об’єднувати два вузли з найменшими частотами, створюючи новий вузол‑корінь.
4. Присвоїти лівому піддереву біт 0, правому — біт 1.
5. Повторювати кроки 3–4, доки не залишиться один вузол (корінь дерева).
6. Пройти дерево, збираючи коди для кожного символу.
7. Замінити символи у тексті їхніми кодами, отримавши стиснутий рядок.

Візуальна інтуїція (текстова)

Текст:  A B C D
Частоти: 5 2 1 1

Heap:
[ (C,1), (D,1), (B,2), (A,5) ]

Об’єднуємо C і D → X(2)
Heap: [ (X,2), (B,2), (A,5) ]

Об’єднуємо X і B → Y(4)
Heap: [ (Y,4), (A,5) ]

Об’єднуємо Y і A → корінь Z(9)
Коди: A=0, B=10, C=110, D=111

Складність

• Час: O(n log n), де n – кількість унікальних символів (підрахунок частот O(n), побудова дерева O(n log n)).
• Пам’ять: O(n) для зберігання частот і дерева.

Код (js)

// 1. Підрахунок частот символів
function countFrequencies(text) {
  const freq = new Map(); // зберігаємо частоти
  for (const ch of text) {
    freq.set(ch, (freq.get(ch) || 0) + 1); // збільшуємо лічильник
  }
  return freq;
}

// 2. Створення вузла дерева
class Node {
  constructor(freq, char = null, left = null, right = null) {
    this.freq = freq;   // частота
    this.char = char;   // символ (null для внутрішніх вузлів)
    this.left = left;
    this.right = right;
  }
}

// 3. Пріоритетна черга (min‑heap) для вузлів
class MinHeap {
  constructor() { this.heap = []; }
  // вставка вузла
  push(node) {
    this.heap.push(node);
    this.bubbleUp(this.heap.length - 1);
  }
  // видалення вузла з найменшою частотою
  pop() {
    if (this.heap.length === 0) return null;
    const min = this.heap[0];
    const end = this.heap.pop();
    if (this.heap.length > 0) {
      this.heap[0] = end;
      this.bubbleDown(0);
    }
    return min;
  }
  bubbleUp(idx) {
    const element = this.heap[idx];
    while (idx > 0) {
      const parentIdx = Math.floor((idx - 1) / 2);
      const parent = this.heap[parentIdx];
      if (element.freq >= parent.freq) break;
      this.heap[idx] = parent; // переміщуємо батька вниз
      idx = parentIdx;
    }
    this.heap[idx] = element; // вставляємо елемент
  }
  bubbleDown(idx) {
    const length = this.heap.length;
    const element = this.heap[idx];
    while (true) {
      let leftIdx = 2 * idx + 1;
      let rightIdx = 2 * idx + 2;
      let swap = null;

      if (leftIdx < length) {
        const left = this.heap[leftIdx];
        if (left.freq < element.freq) swap = leftIdx;
      }

      if (rightIdx < length) {
        const right = this.heap[rightIdx];
        if ((swap === null && right.freq < element.freq) || (swap !== null && right.freq < this.heap[swap].freq)) {
          swap = rightIdx;
        }
      }

      if (swap === null) break;
      this.heap[idx] = this.heap[swap];
      idx = swap;
    }
    this.heap[idx] = element;
  }
}

// 4. Побудова дерева Хаффмана
function buildHuffmanTree(freqMap) {
  const heap = new MinHeap();
  // створюємо листові вузли
  for (const [ch, f] of freqMap.entries()) {
    heap.push(new Node(f, ch));
  }

  // об’єднуємо вузли до одного кореня
  while (heap.heap.length > 1) {
    const left = heap.pop();
    const right = heap.pop();
    const merged = new Node(left.freq + right.freq, null, left, right);
    heap.push(merged);
  }

  return heap.pop(); // корінь дерева
}

// 5. Генерація кодів для символів
function generateCodes(node, prefix = '', codes = {}) {
  if (!node) return;
  // якщо листовий вузол, зберігаємо код
  if (node.char !== null) {
    codes[node.char] = prefix;
    return;
  }
  generateCodes(node.left, prefix + '0', codes); // лівий біт 0
  generateCodes(node.right, prefix + '1', codes); // правий біт 1
}

// 6. Стиснення тексту
function huffmanEncode(text) {
  const freqMap = countFrequencies(text);
  const treeRoot = buildHuffmanTree(freqMap);
  const codes = {};
  generateCodes(treeRoot, '', codes);

  let encoded = '';
  for (const ch of text) {
    encoded += codes[ch];
  }

  return { encoded, codes };
}

// Тестовий приклад
const input = 'this is an example for huffman encoding';
const result = huffmanEncode(input);
console.log(result.encoded); // очікуваний результат: стиснений рядок
console.log(result.codes);   // очікуваний результат: об’єкт з кодами символів

Типові помилки і поради

1. Не враховувати пробіли – вони теж символи, їх частота важлива.
2. Використовувати об’єкт замість Map – при великій кількості символів це знижує швидкість.
3. Не об’єднувати вузли, коли в черзі лише один – це призведе до помилки.
4. Забувати про корінь дерева – без нього коди не будуть сформовані.
5. Не зберігати коди у вигляді рядків – використання масивів бітів зменшить пам’ять.

Перевір себе

1. Яка частота символу визначає його позицію у дереві Хаффмана?
2. Чому рідкісні символи отримують довші коди?

Повне пояснення

Коротке пояснення

Бінарне дерево пошуку (BST) зберігає елементи так, що для будь‑якого вузла всі значення у лівому піддереві менші, а в правому — більші. Це дозволяє швидко вставляти нові елементи і знаходити потрібне значення, порівнюючи його з вузлом за один крок.

Аналогія

Уявіть бібліотеку, де книги розташовані по алфавіту: щоб знайти книгу «Книга», треба спочатку перевірити, чи вона в лівому підрозділі (менша), правому (більша) або саме в поточному розділі.

Коли застосовувати

• Пошук, вставка або видалення елементів у колекції з унікальними ключами.
• Дані, що поступово додаються і не потребують частих перестроювань.
• Коли потрібна швидка (логарифмічна) доступність, а не повний порядок.
• При створенні індексів у базах даних або в реалізації словників.
• Якщо можна прийняти ризик, що дерево може стати незбалансованим.

Кроки алгоритму

1. Починаємо з кореня дерева.
2. Якщо шукане значення менше поточного вузла, переходимо до лівого піддерева.
3. Якщо більше — переходимо до правого піддерева.
4. Повторюємо кроки 2–3, доки не знайдемо вузол з потрібним значенням або досягнемо листа.
5. Якщо елемент не знайдено, повертаємо «не існує».

Візуальна інтуїція (текстова)

          8
        /   \
       3     10
      / \      \
     1   6      14
        / \    /
       4   7  13

Пошук числа 7: 8 → 3 (меньше) → 6 (більше) → 7 (знайдено).

Складність

• Час: у найкращому випадку O(log n), коли дерево збалансоване; у гіршому — O(n) при повному розтягуванні.
• Пам’ять: O(n), бо кожен елемент зберігається у вузлі.

Код (js)

// Клас для вузла BST
class TreeNode {
  constructor(value) { // створюємо новий вузол з заданим значенням
    this.value = value; // значення вузла
    this.left = null;   // ліве піддерево
    this.right = null;  // праве піддерево
  }
}

// Клас BST з методами вставки та пошуку
class BinarySearchTree {
  constructor() { // ініціалізуємо порожнє дерево
    this.root = null;
  }

  // Вставка нового значення у дерево
  insert(value) {
    const newNode = new TreeNode(value);
    if (this.root === null) { // якщо дерево порожнє, новий вузол стає коренем
      this.root = newNode;
      return;
    }
    let current = this.root; // починаємо з кореня
    while (true) {
      if (value < current.value) { // шукаємо місце у лівому піддереві
        if (current.left === null) {
          current.left = newNode; // вставляємо
          return;
        }
        current = current.left; // переходимо ліворуч
      } else if (value > current.value) { // шукаємо у правому піддереві
        if (current.right === null) {
          current.right = newNode;
          return;
        }
        current = current.right; // переходимо праворуч
      } else {
        return; // значення вже існує, не вставляємо дублікати
      }
    }
  }

  // Пошук значення у дереві, повертає вузол або null
  search(value) {
    let current = this.root; // починаємо з кореня
    while (current !== null) {
      if (value === current.value) return current; // знайдено
      if (value < current.value) current = current.left; // ліворуч
      else current = current.right; // праворуч
    }
    return null; // не знайдено
  }
}

// Тестовий приклад
const bst = new BinarySearchTree();
[8, 3, 10, 1, 6, 14, 4, 7, 13].forEach(v => bst.insert(v));
console.log(bst.search(7).value); // очікуваний результат: 7
console.log(bst.search(5));       // очікуваний результат: null

Типові помилки і поради

1. Вставка дубліката – не перевіряти, чи вже існує значення; це призведе до зайвих вузлів.
2. Неправильне порівняння – використовувати === для чисел, а не ==, щоб уникнути типових помилок.
3. Відсутність обробки порожнього дерева – не перевіряти root === null перед пошуком, що викликає помилку.
4. Необґрунтоване балансування – якщо дані вставляються впорядковано, дерево стане лінійним; варто розглянути AVL або Red‑Black дерева.
5. Використання рекурсії без обмеження глибини – у великих деревах може викликати переповнення стеку; краще використовувати ітеративний підхід.

Перевір себе

1. Яка складність пошуку у BST, коли дерево збалансоване?
2. Що відбувається, якщо вставляти значення у вже повністю заповнене дерево без балансування?

Повне пояснення

Коротке пояснення

Алгоритм Хоара шукає елемент, що розташований посередині сортування масиву, без того щоб повністю його упорядкувати. Він працює шляхом рекурсивного розділення масиву на частини, де шуканий елемент зберігається у певному підмасиві.

Аналогія

Уявіть, що ви розділяєте колоду карт на дві частини: одна містить карти, що менші за якусь вибрану карту, а інша – більші. Якщо кількість карт у кожній частині збігається, то вибрана карта є медианою.

Коли застосовувати

• Потрібно знайти середнє значення у великому масиві без сортування.
• Дані не повинні бути вже відсортованими.
• Потрібна швидка оцінка середнього значення, а не точне сортування.
• Коли розмір масиву великий і час сортування критичний.
• При роботі з потоками даних, де можна обробляти частини масиву окремо.

Кроки алгоритму

1. Вибрати «пивот» (наприклад, перший елемент).
2. Перемістити всі менші за пивот елементи ліворуч, більші – праворуч.
3. Після розділення визначити позицію пивоту у новому масиві.
4. Якщо позиція дорівнює шуканому індексу (k‑й), повернути пивот.
5. Якщо позиція більша за k, рекурсивно застосувати алгоритм до лівої частини.
6. Якщо позиція менша за k, рекурсивно застосувати алгоритм до правої частини з коригуванням індексу.

Візуальна інтуїція (текстова)

[7, 2, 5, 3, 9]   // вибираємо пивот = 7
↓
[2, 5, 3] | 7 | [9]
   ↑          ↓
[2, 5, 3]    // позиція пивоту = 3 (0‑індекс)

Складність

У середньому алгоритм працює за O(n) часу, бо кожен елемент розглядається лише один раз. Пам’ять використовується O(1) додатковою, оскільки розділення виконується на місці. У гіршому випадку, коли вибраний пивот завжди найменший або найбільший, складність підвищується до O(n²), але це рідко трапляється.

Код (js)

// Функція для вибору медиани за алгоритмом Хоара
function quickSelectMedian(arr) {
  // Перевірка, що масив не порожній
  if (!Array.isArray(arr) || arr.length === 0) return null;

  // Кількість елементів, за якою шукаємо медиану (0‑індекс)
  const k = Math.floor((arr.length - 1) / 2);

  // Внутрішня рекурсивна функція, що працює на ділянці масиву
  function select(left, right, kIndex) {
    // Якщо ділянка містить один елемент – це наш результат
    if (left === right) return arr[left];

    // Вибираємо пивот – середній елемент ділянки
    const pivotIndex = Math.floor((left + right) / 2);
    const pivotValue = arr[pivotIndex];

    // Переміщуємо пивот у кінець ділянки для простішого розділення
    [arr[pivotIndex], arr[right]] = [arr[right], arr[pivotIndex]];

    // Підготовка до розділення: i – позиція для менших елементів
    let storeIndex = left;
    for (let i = left; i < right; i++) {
      // Якщо елемент менший за пивот, переміщаємо його ліворуч
      if (arr[i] < pivotValue) {
        [arr[storeIndex], arr[i]] = [arr[i], arr[storeIndex]];
        storeIndex++;
      }
    }

    // Повертаємо пивот на його остаточну позицію
    [arr[storeIndex], arr[right]] = [arr[right], arr[storeIndex]];

    // Тепер storeIndex – позиція пивота у відсортованому вигляді
    if (kIndex === storeIndex) {
      return arr[storeIndex];
    } else if (kIndex < storeIndex) {
      // Шукаємо у лівій частині
      return select(left, storeIndex - 1, kIndex);
    } else {
      // Шукаємо у правій частині
      return select(storeIndex + 1, right, kIndex);
    }
  }

  // Запускаємо рекурсію на всьому масиві
  return select(0, arr.length - 1, k);
}

// Тестовий приклад
console.log(quickSelectMedian([3, 1, 4, 2, 5])); // очікуваний результат: 3

Типові помилки і поради

1. Вибір поганого пивота – використання першого елемента може призвести до O(n²). Рекомендується вибирати середній або випадковий елемент.
2. Неправильне оновлення індексу k – при переході в праву частину треба коригувати k, додаючи розмір лівої частини +1.
3. Модифікація вхідного масиву – якщо потрібно зберегти оригінал, робіть копію перед викликом.
4. Перевірка порожнього масиву – без цього функція поверне undefined.
5. Оптимізація – для дуже великих масивів можна застосувати «median‑of‑medians» для гарантованої O(n) складності.

Перевір себе

1. Яка середня складність алгоритму Хоара для вибору медиани?
2. Чому важливо коригувати індекс k при переході в праву частину?

Повне пояснення

Коротке пояснення

Фібоначчі – послідовність, у якій кожен наступний елемент дорівнює сумі двох попередніх. Алгоритм обчислює n‑й член, починаючи з 0 і 1.

Аналогія

Уявіть, що ви підраховуєте кількість кроків у сходинках: кожен новий крок – це сума двох попередніх.

Коли застосовувати

• Потрібно знайти n‑й член послідовності Фібоначчі.
• Вхід – невелике ціле число (наприклад, до 40).
• Потрібна швидка відповідь без надмірного використання пам’яті.
• Не потрібна точність для дуже великих n (наприклад, > 90), коли числа виходять за межі типу Number.

Кроки алгоритму (рекурсія)

1. Якщо n дорівнює 0 або 1, повернути n.
2. Інакше обчислити fib(n‑1) і fib(n‑2).
3. Повернути суму результатів кроку 2.

Кроки алгоритму (динаміка – ітерація)

1. Ініціалізувати prev = 0, curr = 1.
2. Для i від 2 до n виконувати:
   • temp = curr;
   • curr = prev + curr;
   • prev = temp.
3. Повернути curr (або prev, якщо n == 0).

Візуальна інтуїція (текстова)

n=5
prev=0, curr=1
i=2: temp=1 → curr=1, prev=1
i=3: temp=1 → curr=2, prev=1
i=4: temp=2 → curr=3, prev=2
i=5: temp=3 → curr=5, prev=3
результат = 5

Складність

• Рекурсивний варіант: O(2^n) часу, O(n) пам’яті (через стек).
• Ітеративний варіант: O(n) часу, O(1) пам’яті.

Код (js)

// Функція, що обчислює n‑й член послідовності Фібоначчі
function fibIterative(n) {
  // Якщо запитуємо перший або другий елемент, повертаємо їх без обчислень
  if (n === 0) return 0;
  if (n === 1) return 1;

  // Ініціалізуємо змінні для двох попередніх членів
  let prev = 0; // fib(0)
  let curr = 1; // fib(1)

  // Проходимо від 2 до n, обчислюючи новий член як суму двох попередніх
  for (let i = 2; i <= n; i++) {
    const next = prev + curr; // новий член
    prev = curr;              // оновлюємо попередній
    curr = next;              // ставимо новий як поточний
  }

  // Після завершення циклу curr містить fib(n)
  return curr;
}

// Тестовий приклад
console.log(fibIterative(10)); // очікуваний результат: 55

Типові помилки і поради

1. Переповнення стеку – рекурсивний варіант працює лише для невеликих n; використовуйте ітерацію або мемоізацію.
2. Неправильне ініціалізування – не забудьте обробити випадки n = 0 і n = 1, інакше цикл не запрацює.
3. Використання глобальних змінних – залишайте змінні локальними, щоб уникнути конфліктів.
4. Пам’ять – ітеративний підхід потребує лише дві змінні, тоді як рекурсія зберігає стек.
5. Оптимізація – можна використовувати мемоізацію (об’єкт або Map) для збереження вже обчислених значень.

Перевір себе

1. Яка складність ітеративного підходу до обчислення fib(n)?
2. Чому рекурсивний варіант має експоненційну складність?

Повне пояснення

Коротке пояснення

Алгоритм Bellman‑Ford шукає найкоротші шляхи від заданої вершини до всіх інших, дозволяючи графу містити ребра з негативними вагами. Він працює за принципом послідовного розширення відстаней, оновлюючи їх, поки не досягне стабільності або покаже наявність негативного циклу.

Аналогія

Уявіть, що ви плануєте подорож по місту з різними дорогами, де деякі дороги можуть бути «поганими» (негативними). Bellman‑Ford – це як розповідати кожному водієві про новий найкоротший маршрут, повторюючи це кілька разів, доки всі не дізнаються про найкоротший шлях.

Коли застосовувати

• Граф має можливі негативні ваги ребер.
• Потрібно знайти найкоротші шляхи з однієї вершини до всіх інших.
• Необхідно перевірити наявність негативних циклів, що доступні з початкової вершини.
• Кількість вершин невелика (наприклад, до кількох тисяч), бо алгоритм O(V·E).
• Коли інші алгоритми (Dijkstra) недоступні через негативні ваги.

Кроки алгоритму

1. Ініціалізувати відстані: до початкової вершини 0, до всіх інших нескінченність.
2. Для кожної вершини (|V|-1) разів:
   1. Перебрати всі ребра графу.
   2. Якщо відстань до вершини‑початку + вага ребра < відстань до вершини‑кінця, оновити цю відстань.
3. Після ітерацій пройти ще один раз по всіх ребрах: якщо можна зменшити відстань, виявлено негативний цикл.

Візуальна інтуїція (текстова)

Відстані: [0, ∞, ∞]
Ітерація 1:
  (A→B, w=4) → d[B]=4
  (B→C, w=-2) → d[C]=2
Ітерація 2:
  (C→A, w=1) → d[A] не змінюється
  (B→C, w=-2) → d[C] не змінюється
Немає негативного циклу.

Складність

Часова складність: O(V·E), бо |V|-1 ітерацій по всіх ребрах. Пам’ятова складність: O(V), оскільки зберігаються лише масиви відстаней.

Код (js)

// Функція Bellman‑Ford: знаходить найкоротші шляхи з однієї вершини
function bellmanFord(vertices, edges, source) {
  // ініціалізуємо масив відстаней: до початкової вершини 0, інші – нескінченність
  const dist = new Array(vertices).fill(Infinity);
  dist[source] = 0;

  // |V|‑1 разів проходимо по всіх ребрах, оновлюємо відстані
  for (let i = 0; i < vertices - 1; i++) {
    // перебираємо кожне ребро (u, v, w)
    for (const [u, v, w] of edges) {
      // якщо шлях через u до v коротший, оновлюємо
      if (dist[u] + w < dist[v]) {
        dist[v] = dist[u] + w;
      }
    }
  }

  // перевірка наявності негативного циклу: ще один прохід по ребрах
  for (const [u, v, w] of edges) {
    if (dist[u] + w < dist[v]) {
      throw new Error('Граф містить негативний цикл, доступний з вершини ' + source);
    }
  }

  return dist; // повертаємо масив найкоротших відстаней
}

// Тестовий приклад
const vertices = 5;
const edges = [
  [0, 1, 6],
  [0, 2, 7],
  [1, 2, 8],
  [1, 3, 5],
  [1, 4, -4],
  [2, 3, -3],
  [2, 4, 9],
  [3, 1, -2],
  [4, 0, 2],
  [4, 3, 7]
];
console.log(bellmanFord(vertices, edges, 0)); // очікуваний результат: [0, 2, 7, 4, -2]

Типові помилки і поради

1. Неправильна ініціалізація відстаней – забувають встановити нескінченність для всіх вершин, крім початкової. Це призводить до помилкових оновлень.
2. Відсутність перевірки негативного циклу – алгоритм повертає некоректні відстані, якщо в графі є негативний цикл. Завжди додайте останній прохід.
3. Використання «Infinity» як числа – при додаванні до Infinity результат залишається Infinity, тому перевірка dist[u] + w < dist[v] працює правильно.
4. Перевищення меж масиву – індекси вершин повинні бути у діапазоні [0, V‑1]. Перевірте вхідні дані.
5. Оптимізація – якщо граф без негативних циклів, можна зупинити ітерації, коли жодне ребро не оновлює відстань (early exit).

Перевір себе

1. Яка складність Bellman‑Ford у найгіршому випадку? (O(V·E))
2. Чому Bellman‑Ford потрібен, коли Dijkstra працює швидше? (тому що Dijkstra не підтримує негативні ваги).

Повне пояснення

Коротке пояснення

Алгоритм Кадане шукає підмасив з найвищою сумою в заданому масиві. Він працює, додаючи кожен елемент до поточної суми і порівнюючи її з максимумом, а коли сума стає від’ємною – скидає її до нуля.

Аналогія

Уявіть, що ви йдете по схилу: кроки – це елементи масиву, а накопичена сума – ваш підйом. Якщо ви падаєте (сума стає від’ємною), ви знову починаєте підйом з нуля.

Коли застосовувати

• Пошук максимальної суми підмасиву у числовому масиві.
• Дані можуть бути як позитивними, так і негативними числами.
• Потрібен однопрохідний розв’язок без підмасивів.
• Не потрібна конкретна позиція підмасиву, лише її сума.

Кроки алгоритму

1. Ініціалізувати currentSum і maxSum як перший елемент масиву.
2. Для кожного наступного елемента x:
   • Обчислити нову суму: currentSum = Math.max(x, currentSum + x).
   • Оновити максимум: maxSum = Math.max(maxSum, currentSum).
3. Повернути maxSum як результат.

Візуальна інтуїція (текстова)

Масив: [−2, 1, −3, 4, −1, 2, 1, −5, 4]

Крок | x | currentSum | maxSum
-----|---|------------|-------
1    |−2 | −2         | −2
2    | 1 | 1          | 1
3    |−3 | −2         | 1
4    | 4 | 4          | 4
5    |-1 | 3          | 4
6    | 2 | 5          | 5
7    | 1 | 6          | 6
8    |-5 | 1          | 6
9    | 4 | 5          | 6

Складність

• Часова складність: O(n) – один прохід по масиву.
• Пам’ятна складність: O(1) – лише кілька змінних.
• Найгірший випадок: коли всі числа негативні, алгоритм все одно працює за O(n).

Код (js)

// Функція, що повертає максимальну суму підмасиву за алгоритмом Кадане
function kadaneMaxSubarraySum(arr) {
  // Перевірка на порожній масив
  if (arr.length === 0) return 0;

  // Ініціалізуємо поточну суму і максимум як перший елемент
  let currentSum = arr[0]; // накопичувальна сума, що розглядається
  let maxSum = arr[0];     // найвища знайдена сума підмасиву

  // Проходимо по масиву, починаючи з другого елемента
  for (let i = 1; i < arr.length; i++) {
    const x = arr[i];

    // Якщо додавання поточного елемента до currentSum робить його меншим за самий елемент,
    // краще почати новий підмасив з цього елемента
    currentSum = Math.max(x, currentSum + x);

    // Оновлюємо максимум, якщо нова поточна сума більша
    maxSum = Math.max(maxSum, currentSum);
  }

  // Повертаємо знайдену максимальну суму підмасиву
  return maxSum;
}

// Тестовий приклад
console.log(kadaneMaxSubarraySum([-2, 1, -3, 4, -1, 2, 1, -5, 4])); // очікуваний результат: 6

Типові помилки і поради

1. Не обробляти порожній масив – це призведе до помилки доступу до arr[0].
2. Забувати скинути currentSum, коли він стає від’ємним – алгоритм не працюватиме для всіх негативних чисел.
3. Використовувати for...of без індексу – важко отримати попередню суму.
4. Не зберігати максимум – можна втративши найкращий підмасив.
5. Оптимізація: якщо потрібна позиція підмасиву, можна зберігати індекси початку і кінця.

Перевір себе

1. Що робить currentSum = Math.max(x, currentSum + x)?
2. Яка складність пам’яті алгоритму Кадане?

Повне пояснення

Коротке пояснення

Union‑Find (DSU) зберігає елементи у вигляді дерев, де кожен вузол вказує на батька. Операція find повертає корінь дерева, а union об’єднує два дерева, вибираючи менш високий як підлеглий.

Аналогія

Уявіть, що кожен елемент — це учень, а корінь дерева — його керівник. Якщо двоє учнів працюють разом, їхні керівники об’єднуються в одного.

Коли застосовувати

• Потрібно швидко перевіряти, чи два елементи належать одній групі.
• Задача включає багато операцій union і find, наприклад, у графах.
• Необхідна ефективність: O(α(n)) на операцію.
• Коли потрібен розподіл елементів у компоненти зв’язності.

Кроки алгоритму

1. Ініціалізувати масив parent, де кожен елемент сам себе батьком.
2. Ініціалізувати масив rank (висота дерева) нулями.
3. Для find: рекурсивно переходити до батька, застосовуючи path compression.
4. Для union: знайти корені обох елементів, порівняти rank і приєднати менший до більшого.
5. Якщо ranks однакові, збільшити rank нового кореня на 1.

Візуальна інтуїція (текстова)

  a   b
  |   |
  c---d   // після union(a,d)

Складність

Час: амортизована O(α(n)) (почти константна). Пам’ять: O(n) для масивів parent і rank.

Код (js)

// Union‑Find з path compression і union by rank
class UnionFind {
  constructor(size) {
    // parent[i] – батько елемента i
    this.parent = Array.from({ length: size }, (_, i) => i);
    // rank[i] – оцінка висоти дерева, використовується для балансування
    this.rank = Array(size).fill(0);
  }

  // Знаходження кореня елемента з path compression
  find(x) {
    if (this.parent[x] !== x) {
      // рекурсивно шукаємо корінь і «сплющуємо» шлях
      this.parent[x] = this.find(this.parent[x]);
    }
    return this.parent[x];
  }

  // Об’єднуємо два елементи, використовуючи rank
  union(x, y) {
    const rootX = this.find(x);
    const rootY = this.find(y);
    if (rootX === rootY) return; // вже в одній групі

    // Приєднуємо дерево з меншим rank до більшого
    if (this.rank[rootX] < this.rank[rootY]) {
      this.parent[rootX] = rootY;
    } else if (this.rank[rootX] > this.rank[rootY]) {
      this.parent[rootY] = rootX;
    } else {
      // Якщо ranks однакові, підвищуємо rank нового кореня
      this.parent[rootY] = rootX;
      this.rank[rootX] += 1;
    }
  }
}

// Тестовий приклад
const uf = new UnionFind(5);
uf.union(0, 1); // об’єднуємо 0 і 1
uf.union(3, 4); // об’єднуємо 3 і 4
console.log(uf.find(0) === uf.find(1)); // очікуваний результат: true
console.log(uf.find(0) === uf.find(3)); // очікуваний результат: false

Типові помилки і поради

1. Не використовувати path compression – це знижує складність до O(log n). Додайте рекурсивне присвоєння parent[x] = find(parent[x]).
2. Забути про rank – без балансування дерева може стати лінійним, що погіршить час O(n). Додавайте rank і порівнюйте його.
3. Використовувати == замість === – це може призвести до неправильних порівнянь типу.
4. Не ініціалізувати масиви правильно – використовуйте Array.from або заповнювання, щоб уникнути спільних посилань.
5. Забувати про 0‑індексацію – у JS індекси починаються з нуля, тому перевіряйте розміри.

Перевір себе

1. Що робить операція find у Union‑Find?
2. Яка роль масиву rank при об’єднанні двох елементів?

Повне пояснення

Коротке пояснення

Алгоритм Пірсона визначає, скільки мінімальних перестановок треба виконати, щоб відсортувати масив. Він розглядає перестановку як набір циклів і для кожного циклу додає довжину –1 до загальної кількості перестановок.

Аналогія

Уявіть, що кожен елемент – це людина у колі, яка тримає ключ. Кожен ключ повинен потрапити до власника; людина, що тримає неправильний ключ, передає його далі. Коли коло розбивається на підкола (цикли), кількість передач – це довжина –1.

Коли застосовувати

• Вхід – масив цілих чисел, що є перестановкою від 1 до n.
• Необхідно знайти мінімальну кількість обмінів парних елементів.
• Потрібно, щоб після перестановок масив став відсортованим за зростанням.
• Алгоритм працює швидко навіть для великих n (до 10⁶).
• Підходить, коли обмін елементів – дорогий операційний витрат.

Кроки алгоритму

1. Створити масив‑помічник, що відображає поточну позицію кожного числа.
2. Ініціалізувати змінну swaps нульом.
3. Для кожного елемента, якщо він ще не в своєму місці:
   • Запустити цикл, слідкуючи за послідовністю елементів у цьому циклі.
   • Підрахувати довжину циклу len.
   • Додати len-1 до swaps.
4. Повернути значення swaps.

Візуальна інтуїція (текстова)

Масив: [4, 3, 2, 1]
Позиції: 0→3, 1→2, 2→1, 3→0
Цикли: (0 3) і (1 2)
Довжини: 2, 2 → перестановок: (2-1)+(2-1)=2

Складність

Часова складність: O(n) – кожен елемент обробляється один раз. Пам’ятна складність: O(n) – потрібен масив‑помічник довжини n.

Код (js)

// Функція, що повертає мінімальну кількість перестановок для сортування масиву
function minSwapsToSort(arr) {
  const n = arr.length;
  // Копія масиву з індексами, щоб знати поточну позицію кожного елемента
  const indexMap = new Array(n);
  for (let i = 0; i < n; i++) {
    indexMap[arr[i] - 1] = i; // елемент x має бути на позиції x-1
  }

  let swaps = 0; // загальна кількість перестановок
  const visited = new Array(n).fill(false); // чи вже оброблений елемент

  for (let i = 0; i < n; i++) {
    // Якщо елемент вже на своєму місці або вже входить до обробленого циклу
    if (visited[i] || indexMap[i] === i) continue;

    let cycleSize = 0;
    let j = i;
    // Перебираємо елементи циклу
    while (!visited[j]) {
      visited[j] = true;
      j = indexMap[j];
      cycleSize++;
    }

    // Для циклу довжини cycleSize потрібні (cycleSize - 1) перестановок
    if (cycleSize > 0) swaps += cycleSize - 1;
  }

  return swaps;
}

// Тестовий приклад
console.log(minSwapsToSort([4, 3, 2, 1])); // очікуваний результат: 2

Типові помилки і поради

1. Неправильне відображення позицій – пам’ятайте, що елемент x повинен бути на індексі x-1.
2. Відсутність масиву visited – без нього цикл може повторюватися нескінченно.
3. Використання forEach замість звичайного циклу – це може призвести до неправильних індексів.
4. Забудьте про випадок, коли елемент вже на місці – це зменшує кількість обчислень.
5. Оптимізація – можна зменшити пам’ять, використовуючи маркер -1 у масиві замість окремого visited.

Перевір себе

1. Якщо масив вже відсортований, скільки перестановок поверне функція?
2. Як зміниться результат, якщо масив містить дублікатів (не перестановку)?

Повне пояснення

Коротке пояснення

Insertion Sort проходить по масиву, беручи кожен елемент і вставляючи його у правильне місце серед вже відсортованих. Алгоритм базується на ідеї «вставки»: елемент переміщається ліворуч, поки не знайде місце, де попередній елемент менший.

Аналогія

Уявіть, що ви розпоряджаєте колекцію карток у руці: берете одну карту, порівнюєте її з іншими і вставляєте у потрібне місце, не змішуючи решту.

Коли застосовувати

• Невеликий масив (до кількох тисяч елементів).
• Масив вже частково відсортований.
• Потрібна простота реалізації без додаткової пам’яті.
• Коли швидкість не критична, а зрозумілість важлива.

Кроки алгоритму

1. Починаємо з другого елемента (індекс 1).
2. Зберігаємо поточний елемент у змінну key.
3. Порівнюємо key з елементами лівіше, переміщуючи їх вправо, доки не знайдемо місце.
4. Вставляємо key у вільне місце.
5. Переходимо до наступного елемента і повторюємо.

Візуальна інтуїція (текстова)

[5, 2, 4, 6, 1, 3]
   ^
Step 1: key=2, shift 5 right → [5,5,4,6,1,3]
Insert 2: [2,5,4,6,1,3]
   ^
Step 2: key=4, shift 5 right → [2,5,5,6,1,3]
Insert 4: [2,4,5,6,1,3]
   ^
Step 3: key=6, no shift → [2,4,5,6,1,3]
   ^
Step 4: key=1, shift 6,5,4,2 right → [2,2,4,5,6,3]
Insert 1: [1,2,4,5,6,3]
   ^
Step 5: key=3, shift 6,5,4 right → [1,2,4,4,5,6]
Insert 3: [1,2,3,4,5,6]

Складність

• Час: у найгіршому випадку O(n²), у середньому O(n²) при випадкових даних, у кращому — O(n) коли масив вже відсортований.
• Пам’ять: O(1), бо сортування виконується на місці без додаткових структур.

Код (js)

// Сортування вставками: простий, на місці алгоритм
function insertionSort(arr) {
  // Перевірка вхідних даних: масив з мінімум двома елементами
  if (!Array.isArray(arr) || arr.length < 2) return arr;

  // Проходимо по масиву, починаючи з другого елемента (індекс 1)
  for (let i = 1; i < arr.length; i++) {
    const key = arr[i]; // зберігаємо поточний елемент
    let j = i - 1; // індекс останнього елемента в відсортованій частині

    // Переміщуємо елементи, що більші за key, вправо
    while (j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j]; // зсунути елемент на одну позицію праворуч
      j--; // переходимо до попереднього елемента
    }

    // Вставляємо key у знайдене місце
    arr[j + 1] = key;
  }

  return arr; // повертаємо відсортований масив
}

// Тестовий приклад
console.log(insertionSort([5, 2, 4, 6, 1, 3])); // очікуваний результат: [1,2,3,4,5,6]

Типові помилки і поради

1. Забуваєте про індекс 0 – починайте цикл з i = 1, а не 0.
2. Використовуєте arr.splice – це створює нові масиви і збільшує час.
3. Не перевіряєте вхід – якщо масив порожній, цикл не виконається, але варто явно повернути його.
4. Пам’ятайте про O(1) пам’ять – не створюйте додаткових масивів.
5. Оптимізація – для частково відсортованих даних можна додати прапорець, що зупиняє цикл, коли не було переміщень.

Перевір себе

1. Яка складність у найгіршому випадку для Insertion Sort?
2. Чи потребує алгоритм додаткової пам’яті, і якщо так, то скільки?

Повне пояснення

Коротке пояснення

Алгоритм Крускала шукає мінімальне остовне дерево, сортувавши всі ребра за зростанням ваги і додаючи їх послідовно, поки не буде зв’язано всі вершини без циклів.

Аналогія

Уявіть, що ви хочете з’єднати кілька міст мостами так, щоб витрати були мінімальними. Ви спочатку розглядаєте найдешевші мости і додаєте їх, якщо вони не створюють замкненого маршруту.

Коли застосовувати

• Задача про мінімальне остовне дерево у зваженому графі.
• Граф необмежений, може бути роз’єднаним (тоді алгоритм дає мінімальний остов кожної компоненти).
• Потрібна найменша сума ваг.
• Кількість ребер не надто велика, щоб сортування було ефективним.

Кроки алгоритму

1. Сортувати всі ребра за зростанням ваги.
2. Створити структуру «з’єднані компоненти» (Union‑Find).
3. Для кожного ребра у відсортованому списку:
   • Якщо вершини різних компонент, додати ребро до дерева і об’єднати компоненти.
   • Якщо вершини однієї компонент, пропустити ребро (цикл).
4. Після проходу отримати мінімальне остовне дерево.

Візуальна інтуїція (текстова)

Вхід: 5 вершин, 7 ребер
Сортування: (a,b,1) (b,c,2) (c,d,3) (d,e,4) (a,c,5) (b,d,6) (c,e,7)
Крок 1: додати (a,b,1) → дерево
Крок 2: додати (b,c,2) → дерево
Крок 3: додати (c,d,3) → дерево
Крок 4: додати (d,e,4) → дерево (завершено)

Складність

• Час: O(E log E) через сортування ребер; Union‑Find забезпечує амортизовану O(α(V)) на операції.
• Пам’ять: O(E + V) для зберігання ребер і структури Union‑Find.

Код (js)

// Клас для структури Union‑Find (Disjoint Set Union)
class UnionFind {
  constructor(size) {
    // Ініціалізуємо масив батьків, кожен елемент сам собі
    this.parent = Array.from({ length: size }, (_, i) => i);
    // Розмір кожної компоненти (для оптимізації за висотою)
    this.rank = Array(size).fill(0);
  }

  // Знаходимо корінь компоненти з шляхом стиснення
  find(x) {
    if (this.parent[x] !== x) {
      this.parent[x] = this.find(this.parent[x]); // стиснення
    }
    return this.parent[x];
  }

  // Об’єднуємо дві компоненти, повертає true якщо об’єднання відбулося
  union(x, y) {
    const rootX = this.find(x);
    const rootY = this.find(y);
    if (rootX === rootY) return false; // вже в одній компоненті

    // Об’єднуємо за рангом (висотою)
    if (this.rank[rootX] < this.rank[rootY]) {
      this.parent[rootX] = rootY;
    } else if (this.rank[rootX] > this.rank[rootY]) {
      this.parent[rootY] = rootX;
    } else {
      this.parent[rootY] = rootX;
      this.rank[rootX] += 1;
    }
    return true;
  }
}

// Функція Крускала: повертає масив ребер мінімального остовного дерева
function kruskal(vertices, edges) {
  // Крок 1: сортування ребер за зростанням ваги
  const sortedEdges = edges.slice().sort((a, b) => a.weight - b.weight);

  const uf = new UnionFind(vertices); // створюємо структуру для V вершини
  const mst = []; // масив результату

  for (const edge of sortedEdges) {
    const { from, to, weight } = edge;
    // Крок 3: додаємо ребро, якщо не створює цикл
    if (uf.union(from, to)) {
      mst.push(edge);
    }
  }

  return mst;
}

// Тестовий приклад
const vertices = 5; // кількість вершин (0…4)
const edges = [
  { from: 0, to: 1, weight: 1 },
  { from: 1, to: 2, weight: 2 },
  { from: 2, to: 3, weight: 3 },
  { from: 3, to: 4, weight: 4 },
  { from: 0, to: 2, weight: 5 },
  { from: 1, to: 3, weight: 6 },
  { from: 2, to: 4, weight: 7 }
];

console.log(kruskal(vertices, edges)); // очікуваний результат: [{from:0,to:1,w:1},{from:1,to:2,w:2},{from:2,to:3,w:3},{from:3,to:4,w:4}]

Типові помилки і поради

1. Не сортувати ребра – алгоритм працює лише з відсортованим списком.
2. Забути про Union‑Find – без структури об’єднання цикли не виявляються.
3. Використовувати звичайний масив для батьків – це призведе до O(V) пошуку, замість амортизованого O(α(V)).
4. Неправильний індекс вершини – переконайтеся, що вершини нумеруються від 0 до V‑1.
5. Не обробляти роз’єднані графи – алгоритм поверне окремі остовні дерева для кожної компоненти.

Перевір себе

1. Чому сортування ребер за зростанням ваги важливе для Крускала?
2. Як Union‑Find допомагає уникнути циклів під час побудови остовного дерева?

Повне пояснення

Коротке пояснення

Алгоритм підраховує кількість способів скласти задану суму, використовуючи доступні елементи (наприклад, монети). Він працює за принципом динамічного програмування: розв’язує підзадачі, зберігає їх у таблиці і використовує вже знайдені результати.

Аналогія

Уявіть, що ви збираєте пазл: кожен шматок – це елемент, а ціль – повна картинка. Ви зберігаєте вже складені частини, щоб не повторювати роботу.

Коли застосовувати

• Потрібно знайти кількість способів скласти суму з набору чисел.
• Підхід підходить для задач типу «монети» або «розбиття числа».
• Вхід – масив елементів і цільове число.
• Результат – ціле число, що дорівнює кількості розв’язків.
• Підходить для невеликих до середніх розмірів даних.

Кроки алгоритму

1. Ініціалізувати масив dp довжиною target+1, встановити dp[0] = 1.
2. Для кожного елемента в coins:
   • Перебрати всі суми від coin до target.
   • Оновити dp[sum] += dp[sum - coin].
3. Після завершення повернути dp[target].

Візуальна інтуїція (текстова)

coins = [1, 2]
target = 4

dp:   0 1 2 3 4
init: 1 0 0 0 0
after coin=1:
      1 1 1 1 1
after coin=2:
      1 1 2 2 3
result = dp[4] = 3

Складність

• Часова складність: O(n * target), де n – кількість елементів.
• Пам’ятна складність: O(target).

Код (js)

// Функція підраховує кількість способів скласти target з coins
function countWays(coins, target) {
  // Ініціалізуємо масив dp довжиною target+1
  const dp = new Array(target + 1).fill(0);
  // Є один спосіб отримати суму 0 – не брати жодного елемента
  dp[0] = 1;

  // Проходимо по кожному елементу coins
  for (const coin of coins) {
    // Для кожної суми від coin до target
    for (let sum = coin; sum <= target; sum++) {
      // Додаємо кількість способів досягти (sum - coin)
      dp[sum] += dp[sum - coin];
    }
  }

  // Повертаємо кількість способів досягти target
  return dp[target];
}

// Тестовий приклад
console.log(countWays([1, 2], 4)); // очікуваний результат: 3

Типові помилки і поради

1. Не ініціалізувати dp[0] = 1 – без цього алгоритм поверне 0 для будь-якої суми.
2. Перевірити порядок циклів – внутрішній цикл має починатися з coin, а не 0.
3. Використовувати неправильний тип даних – dp повинен бути масивом чисел, а не об’єктами.
4. Не враховувати великий target – для дуже великих сум використовуйте BigInt або модуль.
5. Оптимізація – якщо coins мають однакові значення, можна уникнути дублювання.

Перевір себе

1. Що означає dp[0] = 1 у цьому алгоритмі?
2. Яка складність пам’яті і чому вона така?

Повне пояснення

Коротке пояснення

Алгоритм Першого річка – це пошук найкоротшого шляху в двовимірному полі за допомогою BFS (Breadth‑First Search). Він розглядає усі сусідні клітинки рівномірно, тому перший знайдений шлях до цілі є найкоротшим.

Аналогія

Уявіть, що ви стоїте в центрі лабіринту і розповсюджуєте «світло» рівномірно в усі напрямки. Коли світло дотягується до цілі, це найкоротший шлях.

Коли застосовувати

• Пошук у двовимірному полі (матриці) з клітинками 0/1, де 1 – перешкода.
• Необхідно знайти мінімальну кількість кроків між двома точками.
• Клітинки можна рухати лише вгору, вниз, ліворуч і праворуч.
• Кількість клітинок невелика (до кількох тисяч) – BFS працює швидко.
• Потрібна точність, а не приблизний шлях.

Кроки алгоритму

1. Перевірити, що початкова і кінцева клітинки доступні.
2. Ініціалізувати чергу з початковою точкою і масив відвіданих.
3. Поки черга не порожня:
   • Витягнути поточну клітинку.
   • Якщо це ціль – повернути відстань.
   • Для кожного з чотирьох сусідів: перевірити межі, перешкоди і чи не відвідано.
   • Додати сусіда в чергу з оновленою відстанню.
4. Якщо ціль недоступна – повернути null або -1.

Візуальна інтуїція (текстова)

grid = [
  [0,1,0],
  [0,0,0],
  [1,0,0]
]
start = (0,0)
end   = (2,2)

BFS пошук:
(0,0) → (1,0) → (1,1) → (1,2) → (2,2)
Кількість кроків: 4

Складність

• Часова складність: O(n·m), де n – кількість рядків, m – стовпців.
• Пам’ятна складність: O(n·m) для черги і масиву відвіданих.
• У найгіршому випадку алгоритм розглядає всі клітинки.

Код (js)

// Пошук найкоротшого шляху у двовимірному полі за допомогою BFS
function bfs(grid, start, end) {
  const rows = grid.length;
  const cols = grid[0].length;

  // Перевірка коректності початкових і кінцевих точок
  const [sx, sy] = start;
  const [ex, ey] = end;
  if (grid[sx][sy] !== 0 || grid[ex][ey] !== 0) return null; // недоступна точка

  // Масив відвіданих клітинок
  const visited = Array.from({ length: rows }, () => Array(cols).fill(false));
  // Черга для BFS: кожен елемент – [x, y, distance]
  const queue = [];

  // Ініціалізуємо пошук з початкової точки
  queue.push([sx, sy, 0]);
  visited[sx][sy] = true;

  // Вектор напрямків: вниз, вверх, праворуч, ліворуч
  const directions = [[1,0], [-1,0], [0,1], [0,-1]];

  while (queue.length > 0) {
    const [x, y, dist] = queue.shift(); // витягуємо перший елемент

    if (x === ex && y === ey) return dist; // досягнуто цілі

    for (const [dx, dy] of directions) {
      const nx = x + dx;
      const ny = y + dy;

      // Перевірка меж і перешкод
      if (nx >= 0 && nx < rows && ny >= 0 && ny < cols) {
        if (!visited[nx][ny] && grid[nx][ny] === 0) {
          visited[nx][ny] = true;
          queue.push([nx, ny, dist + 1]);
        }
      }
    }
  }

  return null; // ціль недоступна
}

// Маленький тестовий приклад
const grid = [
  [0, 1, 0],
  [0, 0, 0],
  [1, 0, 0]
];
console.log(bfs(grid, [0, 0], [2, 2])); // очікуваний результат: 4

Типові помилки і поради

1. Не перевіряти, чи клітинка – перешкода: це призводить до нескінченного циклу.
2. Використовувати for...in для масивів: індекси будуть рядками, що викликає помилки.
3. Забути про відвідані клітинки: алгоритм може повторно обробляти ті ж позиції, збільшуючи час.
4. Неправильний порядок напрямків: не критично, але може вплинути на шлях у випадку декількох рішень.
5. Використання рекурсії замість черги: викликає переповнення стеку для великих полів.

Перевір себе

1. Яка складність часу має BFS у двовимірному полі?
2. Чому важливо маркувати клітинки як відвідані під час пошуку?

Повне пояснення

Коротке пояснення

Алгоритм Дейкстри шукає найкоротший шлях від однієї вершини до всіх інших у графі з невід’ємними вагами, використовуючи пріоритетну чергу для вибору вершини з найменшою відстанню.

Аналогія

Уявіть, що ви плануєте подорож по місту: кожен вузол – це місце, а ребра – дороги з часом руху. Ви завжди вибираєте наступне місто, яке можна дістатися за найменший час з того, де ви зараз.

Коли застосовувати

• граф із невід’ємними вагами;
• потрібен найкоротший шлях від однієї вершини до всіх інших;
• граф не надто великий, щоб використовувати O(V^2) варіант;
• потрібна швидка реакція на запити про шлях.

Кроки алгоритму

1. Ініціалізувати відстані: 0 для стартової вершини, ∞ для всіх інших.
2. Додати усі вершини до пріоритетної черги з їхніми відстанями.
3. Поки черга не порожня:
   1. Витягнути вершину з найменшою відстанню.
   2. Для кожного сусіда перевірити, чи нова відстань через цю вершину менша за поточну; якщо так – оновити відстань і шлях, а також оновити позицію у черзі.
4. Після завершення отримати таблицю мінімальних відстаней і шляхів.

Візуальна інтуїція (текстова)

Вершини: A B C D
Відстані: 0 ∞ ∞ ∞
Черга: (A,0)

Витяг A → B: нова відстань 5 → оновити
Черга: (B,5)

Витяг B → C: нова відстань 9 → оновити
Черга: (C,9)

Складність

Часова складність: O((V+E) log V) з пріоритетною чергою; просторовий: O(V+E). У найгіршому випадку, коли використовується простий масив замість черги, складність підвищується до O(V^2).

Код (js)

// Дейкстра – пошук найкоротшого шляху у графі з невід’ємними вагами
// graph – об’єкт, де ключі – вершини, значення – масив пар [сусід, вага]
function dijkstra(graph, start) {
  // 1. Ініціалізуємо відстані: 0 для старту, ∞ для всіх інших
  const distances = {};
  for (const vertex in graph) {
    distances[vertex] = Infinity; // ініціалізуємо
  }
  distances[start] = 0;

  // 2. Створюємо пріоритетну чергу (масив + сортування)
  const priorityQueue = [];
  for (const vertex in graph) {
    priorityQueue.push({ node: vertex, distance: distances[vertex] });
  }

  // 3. Поки черга не порожня
  while (priorityQueue.length > 0) {
    // сортуємо за відстанню, щоб отримати вершину з мінімальною
    priorityQueue.sort((a, b) => a.distance - b.distance);
    const { node: currentVertex, distance: currentDistance } = priorityQueue.shift();

    // Якщо поточна відстань більша за збережену, пропускаємо
    if (currentDistance > distances[currentVertex]) continue;

    // 4. Перевіряємо сусідів
    for (const [neighbor, weight] of graph[currentVertex]) {
      const newDistance = distances[currentVertex] + weight;
      if (newDistance < distances[neighbor]) {
        // 5. Оновлюємо відстань
        distances[neighbor] = newDistance;
        // 6. Оновлюємо позицію у черзі
        const index = priorityQueue.findIndex(v => v.node === neighbor);
        if (index !== -1) {
          priorityQueue[index].distance = newDistance;
        } else {
          priorityQueue.push({ node: neighbor, distance: newDistance });
        }
      }
    }
  }

  return distances;
}

// Тестовий приклад
const graph = {
  A: [['B', 5], ['C', 2]],
  B: [['A', 5], ['C', 1], ['D', 3]],
  C: [['A', 2], ['B', 1], ['D', 8]],
  D: [['B', 3], ['C', 8]]
};
console.log(dijkstra(graph, 'A')); // очікуваний результат: { A: 0, B: 5, C: 2, D: 8 }

Типові помилки і поради

1. Використання простого масиву замість черги – призводить до O(V^2) часу. Використайте PriorityQueue або бібліотеку.
2. Не оновлювати відстань, якщо нова більша – це знижує ефективність. Перевірте умову newDistance < distances[neighbor].
3. Забудьте про відсутність ваг – у графі з негативними вагою Дейкстра не працює. Перевірте дані перед запуском.
4. Не обробляйте вершини, що вже були «закриті» – це можна уникнути перевіркою currentDistance > distances[currentVertex].
5. Оптимізація – використайте двійкову купу (binary heap) замість сортування масиву, щоб зменшити час на O((V+E) log V).

Перевір себе

1. Чому Дейкстра не працює з негативними вагами?
2. Яка складність у найгіршому випадку, якщо використовувати простий масив замість купи?

Повне пояснення

Коротке пояснення

Алгоритм Форда‑Фулькера шукає послідовно збільшуючі шляхи від джерела до стоку, додаючи потік по кожному знайденому шляху. Коли більше шляхів не існує, отриманий потік є максимальним.

Аналогія

Уявіть, що мережа – це система річок з різними ширинами; алгоритм поступово розширює потік, доки не заповнить всі доступні «труби».

Коли застосовувати

• Задачі про транспорт, логістика або мережевий трафік.
• Мережа з неотрицательними пропускними способностями.
• Потрібен точний максимум, а не лише оцінка.
• Вхід – граф у вигляді списку суміжності або матриці.
• Потрібно обчислити потік між конкретними вершинами‑джерелом і стоком.

Кроки алгоритму

1. Ініціалізувати потік у всіх ребрах нульовим.
2. Знайти в графі шляхи, що збільшують потік (BFS/DFS), використовуючи залишкові пропускні способності.
3. Якщо шлях знайдено, визначити мінімальну залишкову пропускність по цьому шляху.
4. Додати цей мінімум до потоку кожного ребра на шляху і оновити залишкові пропускності.
5. Повторювати кроки 2–4, доки нові шляхи не будуть знайдені.
6. Повернути сумарний потік як результат.

Візуальна інтуїція (текстова)

  source
    | 5
    v
   (1) --3--> (2)
    |          |
  4|          |2
    v          v
   (3) --6--> sink

Перший шлях: source→1→2→sink (мін. 3). Потім оновлюємо пропускності і шукаємо новий шлях: source→3→sink (мін. 4). Після двох ітерацій потік = 7.

Складність

Часова складність: O(VE²) у найгіршому випадку, де V – кількість вершин, E – ребер. Пам’ятна складність: O(V+E) для зберігання графу і залишкових пропускностей.

Код (js)

// Функція для знаходження максимального потоку за алгоритмом Форда‑Фулькера
function fordFulkerson(graph, source, sink) {
  // graph – об’єкт, ключі – вершини, значення – масив ребер {to, capacity}
  const residual = {}; // залишкові пропускності

  // ініціалізуємо залишкову мережу
  for (const u in graph) {
    residual[u] = [];
    for (const edge of graph[u]) {
      // додаємо пряме ребро
      residual[u].push({ to: edge.to, capacity: edge.capacity });
      // додаємо зворотне ребро з нульовою пропускністю
      residual[edge.to] = residual[edge.to] || [];
      residual[edge.to].push({ to: u, capacity: 0 });
    }
  }

  let maxFlow = 0; // загальний потік

  while (true) {
    // ініціалізуємо BFS: черга, відвідані вершини і шлях
    const queue = [source];
    const visited = new Set([source]);
    const parent = {}; // зберігаємо попередника і ребро

    while (queue.length && !visited.has(sink)) {
      const u = queue.shift();
      for (const edge of residual[u]) {
        if (!visited.has(edge.to) && edge.capacity > 0) {
          visited.add(edge.to);
          parent[edge.to] = { from: u, edge };
          queue.push(edge.to);
        }
      }
    }

    // якщо шлях не знайдено, завершуємо цикл
    if (!visited.has(sink)) break;

    // знаходимо мінімальну пропускність по знайденому шляху
    let pathFlow = Infinity;
    for (let v = sink; v !== source; v = parent[v].from) {
      pathFlow = Math.min(pathFlow, parent[v].edge.capacity);
    }

    // оновлюємо пропускності по шляху
    for (let v = sink; v !== source; v = parent[v].from) {
      const u = parent[v].from;
      // зменшуємо пряме ребро
      const e = residual[u].find(e => e.to === v);
      e.capacity -= pathFlow;
      // збільшуємо зворотне ребро
      const rev = residual[v].find(e => e.to === u);
      rev.capacity += pathFlow;
    }

    maxFlow += pathFlow; // додаємо до загального потоку
  }

  return maxFlow;
}

// Тестовий приклад
const graph = {
  source: [{ to: '1', capacity: 10 }, { to: '2', capacity: 5 }],
  '1': [{ to: '3', capacity: 4 }, { to: '2', capacity: 15 }],
  '2': [{ to: '4', capacity: 10 }],
  '3': [{ to: sink, capacity: 10 }],
  '4': [{ to: sink, capacity: 10 }]
};
const sink = 'sink';
console.log(fordFulkerson(graph, 'source', sink)); // очікуваний результат: 15

Типові помилки і поради

1. Неправильне оновлення залишкових ребер – переконайтеся, що зворотні ребра створюються лише один раз.
2. Використання DFS замість BFS – це може призвести до O(VE) у найгіршому випадку; BFS гарантує швидший збіг.
3. Забудьте про нульові пропускності – вони потрібні для зворотних ребер, інакше алгоритм не працюватиме.
4. Не перевіряйте наявність вершини‑стоку – якщо вона відсутня, алгоритм завершиться помилкою.
5. Оптимізація – використовуйте алгоритм Едмонда‑Карпа (BFS) замість простого DFS, щоб досягти O(VE²).

Перевір себе

1. Яка залишкова пропускність після першої ітерації у тестовому прикладі?
2. Чому BFS використовується для пошуку шляхів у Ford‑Fulkerson?