Які бувають види алгоритмів за структурою?

АлгоритмиJunior~3 хв читання

Коротка відповідь

Лінійні (послідовні) - кроки виконуються строго один за одним.
Розгалужені (з розгалуженнями) - вибір однієї з гілок виконання за умовою.
Циклічні (ітераційні) - повторення блоку дій, поки виконується умова або заданий діапазон.
Рекурсивні - алгоритм викликає сам себе до настання базового випадку (частіше розглядається як техніка організації, але виділяється окремо).
Комбіновані - поєднують перелічені структури керування в одному рішенні.

У структурному програмуванні виділяють три базові керуючі структури: послідовність, розгалуження і цикл. Рекурсія - ключова техніка, яку часто розглядають окремо. Реальні алгоритми зазвичай комбінують кілька структур.

1) Лінійні (послідовні)

Виконуються крок за кроком без розгалужень і повторень. Застосовні, коли порядок дій фіксований і не залежить від умов.

Переваги: простота, передбачуваність, легка перевірюваність.
Коли застосовувати: форматування даних, обчислення агрегатів, підготовка значень перед валідацією.
Типові помилки: зайві кроки, дублювання коду, відсутність обробки крайніх випадків.

javascript

function normalizeName(name) {
  return name.trim().toLowerCase().replace(/\s+/g, ' ');
}

function avg(nums) {
  if (!nums.length) return 0;
  let sum = 0;
  for (const n of nums) sum += n;
  return sum / nums.length;
}

const raw = "  Alice   Bob  ";
const normalized = normalizeName(raw);
const mean = avg([10, 20, 30]);
console.log({ normalized, mean: mean.toFixed(2) });

2) Розгалужені (з розгалуженнями)

Вибір однієї з альтернатив за умовою. Основні конструкції: if/else, switch/case, тернарний оператор.

if / else - універсальний вибір за умовами.
switch - зручно для дискретних значень.
Тернарний ? : - для простих присвоєнь за умовою.

javascript

function grade(score) {
  if (score < 0 || score > 100) return "invalid"; // гвард-кейс
  if (score >= 90) return "A";
  if (score >= 75) return "B";
  if (score >= 60) return "C";
  if (score >= 40) return "D";
  return "F";
}

console.log([95, 76, 12, 101].map(grade));

Слідкуйте за повнотою умов (обробіть крайні випадки).
Розташовуйте перевірки від більш строгих до менш строгих (або навпаки, але послідовно).
Уникайте "драбинок" if-else, якщо можна замінити на таблицю відповідностей/мапу.

3) Циклічні (ітераційні)

Багаторазове виконання блоку коду. Види: for, while, do...while, а також ітеровані форми (for...of) і методи вищого порядку (forEach, map) - вони логічно теж реалізують повторення.

for - відома кількість ітерацій або перебір по колекції.
while - поки умова істинна; do...while - мінімум одна ітерація.
break/continue - керування потоком у циклі.

javascript

function sumUntilLimit(arr, limit) {
  let sum = 0;
  for (const n of arr) {
    if (sum + n > limit) break; // ранній вихід
    sum += n;
  }
  return sum;
}

console.log(sumUntilLimit([5, 3, 8, 2], 10)); // 8

Визначте інваріант - що залишається істинним на кожній ітерації.
Слідкуйте за зміною лічильників/умов, щоб уникнути нескінченних циклів.
Використовуйте ранні виходи (break/return), щоб не робити зайвих ітерацій.

Рекурсивні алгоритми

Рекурсія - спосіб розв'язання задач через розбиття на підзадачі того самого типу з базовим випадком. Особливо зручна для дерев, графів, розбиттів (divide and conquer).

javascript

const tree = {
  value: 1,
  children: [
    { value: 2, children: [] },
    { value: 3, children: [ { value: 4, children: [] } ] }
  ]
};

function dfs(node, visit) {
  if (!node) return; // базовий випадок
  visit(node.value);
  for (const child of node.children || []) {
    dfs(child, visit); // рекурсивний крок
  }
}

dfs(tree, v => console.log(v)); // 1, 2, 3, 4

Обов'язково визначте базовий випадок і прогрес до нього, інакше буде переповнення стека.
Хвостова рекурсія може бути оптимізована компілятором/рушієм, але не всюди (у JS - немає гарантії).
Ітеративна версія через явний стек/чергу часто економить стек викликів і краще контролює пам'ять.

javascript

function dfsIter(root, visit) {
  if (!root) return;
  const stack = [root];
  while (stack.length) {
    const node = stack.pop();
    visit(node.value);
    const children = node.children || [];
    for (let i = children.length - 1; i >= 0; i--) {
      stack.push(children[i]);
    }
  }
}

dfsIter(tree, v => console.log(v)); // 1, 2, 3, 4

Комбіновані алгоритми

На практиці алгоритми зазвичай комбінують послідовні кроки, розгалуження і цикли. Приклад: валідація форми - лінійний прохід по полях (цикл) із перевіркою правил (розгалуження) і попередньою обробкою (послідовність).

javascript

function validateForm(fields) {
  const errors = [];
  for (const f of fields) { // цикл
    const value = String(f.value ?? "").trim(); // лінійна попередня обробка
    if (f.required && value === "") { // розгалуження
      errors.push(`${f.name}: required`);
      continue;
    }
    if (f.type === "email") {
      const ok = /^[^\s@]+@[^\s@]+\.[^\s@]+$/.test(value);
      if (!ok) errors.push(`${f.name}: invalid email`);
    } else if (f.type === "age") {
      const age = Number(value);
      if (!Number.isInteger(age) || age < 0 || age > 120) {
        errors.push(`${f.name}: invalid age`);
      }
    }
  }
  return errors;
}

console.log(
  validateForm([
    { name: "email", type: "email", required: true, value: " user@example.com " },
    { name: "age", type: "age", required: false, value: "200" }
  ])
);

Коротка зведена таблиця

Тип	Ключова ідея	JS-конструкції	Де застосовуються
Лінійні	Послідовність кроків	Послідовні вирази	Форматування, агрегування
Розгалужені	Вибір гілки за умовою	if/else, switch, ?:	Валідація, маршрутизація
Циклічні	Повторення до умови/по діапазону	for, while, do...while, for...of	Перебір колекцій, пошук, агрегації
Рекурсивні	Самозастосування до підзадач	Функції, що викликають самі себе	Дерева, графи, divide and conquer
Комбіновані	Змішування структур	Комбінація вищезазначеного	Реальні застосунки і сервіси

Що можуть запитати на співбесіді

Наведіть приклади лінійного, розгалуженого і циклічного алгоритмів та їхню складність за часом/пам'яттю.
Коли рекурсія переважніша за ітерацію, і навпаки? Як переписати рекурсивний код ітеративно.
Намалюйте блок-схему алгоритму з розгалуженнями і циклами для заданої задачі.
Де додати ранні виходи (guard clauses) і чому це спрощує код.

Порада: перед кодом накидайте псевдокод, відзначте базові випадки та інваріанти - це знижує кількість помилок.

Коротка відповідь

Для співбесіди

Premium

Коротка відповідь допоможе вам впевнено відповідати на цю тему під час співбесіди.