Які властивості повинен мати алгоритм?

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

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

Скінченність: алгоритм зобов'язаний завершуватися за скінченну кількість кроків.
Визначеність (однозначність): кожна інструкція сформульована однозначно; на кожному кроці немає двозначності.
Дискретність: процес складається з окремих, чітко відокремлених кроків.
Масовість (загальність): алгоритм застосовний до цілого класу вхідних даних, а не до єдиного прикладу.
Результативність і коректність: для допустимих входів отримується результат, що задовольняє специфікацію.
Ефективність: розумні витрати часу і пам'яті; оцінювана обчислювальна складність.

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

Нижче - ключові властивості алгоритму, навіщо вони потрібні на практиці і як розпізнати їх на прикладах.

1) Скінченність (зупинка)

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

Перевірка: чи є інваріант і спадна міра, яка строго скорочується на кожному циклі і досягає базового випадку?
Ознака проблеми: цикл/рекурсія без умови виходу, яка гарантовано стане істинною.

// Приклад порушення скінченності:
function loopForever() {
  while (true) {
    // немає спадної міри і умови виходу
  }
}

2) Визначеність (однозначність інструкцій)

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

// Погано (невизначеність):
// "Виконати обробку вводу"
// Не ясно: що саме і як?

// Добре (визначено):
function normalize(input) {
  // 1) trim пробіли по краях
  // 2) перевести у нижній регістр
  // 3) замінити послідовності пробілів одним пробілом
  return input.trim().toLowerCase().replace(/\s+/g, ' ');
}

3) Дискретність

Алгоритм повинен складатися з послідовності елементарних кроків, кожен з яких виконуваний і має спостережуваний ефект. Це дозволяє аналізувати коректність і складність по кроках.

// Дискретні кроки сортування вибором (описані явно):
function selectionSort(a) {
  const n = a.length;
  for (let i = 0; i < n - 1; i++) {             // крок: вибір позиції i
    let min = i;                                 // крок: припускаємо мінімум
    for (let j = i + 1; j < n; j++) {            // крок: пошук мінімуму в хвості
      if (a[j] < a[min]) min = j;                // крок: оновлення мінімуму
    }
    if (min !== i) [a[i], a[min]] = [a[min], a[i]]; // крок: обмін
  }
  return a;
}

4) Масовість (загальність)

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

// Бінарний пошук працює для будь-якого відсортованого масиву порівнюваних елементів
// (передумова: масив відсортований за незростанням)
function binarySearch(arr, x) {
  let l = 0, r = arr.length - 1;
  while (l <= r) {
    const m = l + ((r - l) >> 1);
    if (arr[m] === x) return m;      // постумова: індекс знайденого елемента
    if (arr[m] < x) l = m + 1; else r = m - 1;
  }
  return -1;                         // якщо елемента немає
}

5) Результативність і коректність

Результативність: алгоритм завжди видає якийсь результат для допустимих входів. Коректність: цей результат задовольняє специфікацію (постумовам). Доказовість коректності - найважливіша вимога до алгоритмів, що використовуються в продакшені.

// Специфікація (словами):
// Вхід: невід'ємні цілі a, b, не обидва нулі.
// Вихід: gcd(a, b) - найбільший спільний дільник, тобто d | a, d | b і
// для будь-якого d' | a і d' | b вірно d' <= d.

function gcd(a, b) {
  while (b !== 0) {
    const t = a % b;
    a = b;
    b = t;
  }
  return Math.abs(a);
}

// Коректність ескізно:
// - Інваріант: gcd(a, b) не змінюється при заміні (a, b) := (b, a mod b).
// - Термінація: b зменшується за модулем і досягає 0 за скінченну кількість кроків.
// - Постумова: коли b = 0, відповідь a - шуканий НСД.

6) Ефективність (складність за часом і пам'яттю)

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

Час: скільки елементарних операцій виконується (наприклад, O(n log n)).
Пам'ять: додатковий обсяг пам'яті (наприклад, O(1) у Евкліда).
Компроміси: час ↔ пам'ять, точність ↔ швидкість тощо.

// Наївний НСД (неефективний): O(min(a,b))
function gcdNaive(a, b) {
  let d = Math.min(a, b);
  while (d > 0) {
    if (a % d === 0 && b % d === 0) return d;
    d--;
  }
}

// Евклід ефективніший: O(log min(a,b)) кроків.

Пов'язані поняття, які часто запитують

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

Підсумкова вижимка (для відповіді на співбесіді)

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

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

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

Premium

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