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

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

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

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

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

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

Premium

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