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

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

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

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

Контент

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

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

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

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

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

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

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

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

### Визначення

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

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

- **Вхідні дані:** зазначено, які дані алгоритм приймає (можуть бути й порожніми).
- **Вихід (результат):** чітко визначено, що алгоритм повертає і в якому форматі.
- **Скінченність:** виконання завершується за скінченну кількість кроків.
- **Детермінованість (однозначність):** при однакових вхідних даних результат і послідовність дій передбачувані (або задана ймовірнісна модель, якщо алгоритм рандомізований).
- **Дискретність:** алгоритм складається з окремих, виконуваних елементарних кроків.
- **Масовість (універсальність):** розв'язує не один конкретний приклад, а цілий клас задач (усі входи, що задовольняють умовам).
- **Коректність (результативність):** для допустимих входів видає правильний результат, що відповідає специфікації.
- **Ефективність і складність:** оцінка витрат за часом і пам'яттю. Часто використовують 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.
- **Безпека і хеші:** хеш-функції, порівняння підпису, перевірка цілісності.

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

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

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

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

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

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

Для рев’юера

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

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