Що таке алгоритм?

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

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

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

Розгорнута відповідь

Визначення

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

Ключові властивості

Вхідні дані: зазначено, які дані алгоритм приймає (можуть бути й порожніми).
Вихід (результат): чітко визначено, що алгоритм повертає і в якому форматі.
Скінченність: виконання завершується за скінченну кількість кроків.
Детермінованість (однозначність): при однакових вхідних даних результат і послідовність дій передбачувані (або задана ймовірнісна модель, якщо алгоритм рандомізований).
Дискретність: алгоритм складається з окремих, виконуваних елементарних кроків.
Масовість (універсальність): розв'язує не один конкретний приклад, а цілий клас задач (усі входи, що задовольняють умовам).
Коректність (результативність): для допустимих входів видає правильний результат, що відповідає специфікації.
Ефективність і складність: оцінка витрат за часом і пам'яттю. Часто використовують Big-O: O(1), O(log n), O(n), O(n log n), O(n²) тощо; окремо оцінюють пам'ять.

Приклади алгоритмів

Лінійний пошук: послідовно перевіряє елементи. Час - O(n), пам'ять - O(1).
Бінарний пошук: шукає у відсортованому масиві, ділячи діапазон навпіл. Час - O(log n), пам'ять - O(1). Вимагає попереднього сортування.
Сортування: швидке сортування - O(n log n) у середньому, O(n²) у найгіршому; сортування вставками - O(n²), але добре на майже відсортованих даних.
Хешування: пошук/вставка у хеш-таблицю - O(1) у середньому, O(n) у найгіршому.

Приклад коду

// Лінійний пошук - O(n) за часом, O(1) за пам'яттю
function linearSearch(arr, x) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === x) return i;
  }
  return -1;
}

// Бінарний пошук - O(log n) за часом, O(1) за пам'яттю (масив має бути відсортований)
function binarySearch(sorted, x) {
  let l = 0, r = sorted.length - 1;
  while (l <= r) {
    const m = l + ((r - l) >> 1);
    if (sorted[m] === x) return m;
    if (sorted[m] < x) l = m + 1;
    else r = m - 1;
  }
  return -1;
}

// Швидке сортування (quicksort) - середнє O(n log n), найгірше O(n^2)
function quickSort(a) {
  if (a.length <= 1) return a;
  const pivot = a[a.length >> 1];
  const left = [], mid = [], right = [];
  for (const v of a) {
    if (v < pivot) left.push(v);
    else if (v > pivot) right.push(v);
    else mid.push(v);
  }
  return [...quickSort(left), ...mid, ...quickSort(right)];
}

// Приклад використання
const data = [5, 1, 9, 2, 7, 3];
const sorted = quickSort(data);           // [1,2,3,5,7,9]
const idx1 = linearSearch(sorted, 7);     // 4
const idx2 = binarySearch(sorted, 7);     // 4 (швидше на великих n)

Алгоритми у веб-розробці

Пошук і фільтрація в інтерфейсах: дебаунс/троттлінг обробників вводу, ефективні фільтри O(n) або індексація.
Рендеринг і діфінг: алгоритми порівняння дерева (віртуальний DOM), мінімізація перемальовувань.
Маршрутизація і кешування: пошук маршрутів, LRU-кеші для даних і асетів (service worker).
Обробка подій і черг: батчинг, тайм-слайсинг, планування завдань у event loop.
Безпека і хеші: хеш-функції, порівняння підпису, перевірка цілісності.

Як відповідати на співбесіді

Дайте чітке визначення: що таке алгоритм і його мета.
Перелічіть ключові властивості (вхід/вихід, скінченність, детермінованість, коректність, складність).
Згадайте оцінку складності: час і пам'ять, Big-O.
Наведіть 1-2 приклади (лінійний/бінарний пошук, сортування) і короткий код.
Пов'яжіть із практикою веб-розробки: як ви застосовували це в проекті.

Приклад короткої відповіді: Алгоритм - це скінченна послідовність однозначних кроків для розв'язання задачі. Важливі вхід і вихід, коректність і ефективність. Наприклад, бінарний пошук у відсортованому масиві працює за O(log n) за часом і O(1) за пам'яттю; я застосовував його для прискорення пошуку по попередньо відсортованому списку.

Типові пастки

Плутати «алгоритм» і «реалізацію мовою»: визначення має бути технологічно нейтральним.
Не згадати вхід/вихід чи скінченність: ці критерії обов'язкові.
Ігнорувати складність: завжди говоріть про час і пам'ять у термінах Big-O.
Помилки в передумовах: наприклад, бінарний пошук працює тільки на відсортованих даних.

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

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

Premium

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