Запропонувати правку

Покращити цю статтю

Допрацюйте відповідь до «Які властивості повинен мати алгоритм?». Ваші зміни проходять модерацію перед публікацією.

Потрібне підтвердження

Контент

Що ви змінюєте

Заголовок (UA)

Коротка відповідь (UA)

Показується над повною відповіддю для швидкого нагадування.

Відповідь (UA)

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

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

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

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

### 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 недетермінованість: алгоритм може бути недетермінованим, але його специфікація і коректність повинні бути визначені (наприклад, будь-який допустимий результат з множини).
- Доказовість: інваріанти циклів, рекурсивні базові випадки, спадна міра, часткова/тотальна коректність.

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

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

Markdown · перетягуйте зображення · ⌘B / ⌘I шорткати798 слів

Для рев’юера

Примітка для модератора (необов’язково)

Бачить лише модератор. Прискорює рев’ю.