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

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

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

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

Контент

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

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

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

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

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

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

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

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

### Визначення і контекст

- Лінійний за структурою: послідовність кроків без умов (if/switch) і циклів (for/while). Траєкторія виконання одна й та сама для будь-якого входу.
- Лінійний за часом (O(n)): час роботи зростає лінійно від розміру входу. Такий алгоритм може містити цикли або рекурсію, але кожен елемент входу обробляється фіксовану кількість разів.

### Приклади реалізації

#### 1) Лінійний за структурою (без розгалужень і циклів)

Простий приклад на JavaScript: обчислюємо площу і периметр прямокутника за заданими сторонами.

```javascript
const a = 5; // сторона A
const b = 3; // сторона B

const area = a * b;
const perimeter = 2 * (a + b);

console.log('Площа:', area);
console.log('Периметр:', perimeter);

// Немає ні умов, ні циклів - виконання строго згори вниз.
```

#### 2) Лінійний за часом O(n)

Сумування елементів масиву - лінійна часова складність: кожен елемент відвідується один раз.

```javascript
function sum(arr) {
  let s = 0;
  for (const x of arr) {
    s += x; // кожен елемент обробляється рівно один раз
  }
  return s;
}

console.log(sum([1, 2, 3, 4])); // 10
```

Тут присутній цикл, отже за структурою це не лінійний алгоритм, однак за часом - лінійний (O(n)).

### Як відрізняти на співбесіді

- Якщо йдеться про структуру: немає розгалужень і циклів - це лінійний за структурою.
- Якщо йдеться про складність: оцінюємо залежність часу/пам'яті від n. Один прохід по даних - O(n) - лінійний за часом.
- Уточнюйте термін: "лінійний за структурою чи лінійна складність (O(n))?"

### Типові помилки і питання

- Плутанина між "лінійним алгоритмом" як послідовністю кроків і "лінійною складністю" O(n).
- Вважати, що цикл завжди означає нелінійну складність. Цикл може бути і лінійним, і квадратичним - залежить від кількості вкладень і повторів.
- Ігнорувати пам'ять: є алгоритми, лінійні за часом, але не за пам'яттю (наприклад, створюють масив розміром n).

### Порівняння з іншими класами (за часом)

- O(1) - стала: приклад - доступ до елемента масиву за індексом.
- O(log n) - логарифмічна: бінарний пошук по відсортованому масиву.
- O(n log n) - типово для ефективних сортувань (merge/quick у середньому).
- O(n^2) - квадратична: вкладені цикли по одному й тому самому набору даних.

### Коли застосовувати

- Лінійна структура - коли алгоритм повинен бути максимально простим і передбачуваним (виконання фіксованим ланцюжком дій).
- Лінійна складність - коли потрібна масштабована обробка великих вхідних даних одним проходом (streaming/iterative processing).

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

Для рев’юера

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

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