Skip to main content

Що означає O(n) - лінійна складність?

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

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

O(n) - лінійна складність: час виконання (чи кількість елементарних операцій) зростає пропорційно розміру входу n. Якщо збільшити n удвічі, час приблизно подвоїться. Це зазвичай відповідає одному повному проходу по даних без вкладених циклів, що залежать від n.

Детально

Що означає «лінійна»

Лінійна складність описується функцією вигляду a·n + b: константи a і b відкидаються в нотації O(·), тому отримуємо O(n). Інтуїтивно: кожне додавання елемента додає приблизно однакову кількість роботи, а повний прохід по масиву довжини n дає сумарно n кроків.

  • Один цикл по даних без вкладених від n операцій - O(n).
  • Кілька незалежних проходів: O(n) + O(n) = O(n).
  • Ранній вихід можливий, але класична оцінка - за найгіршим випадком: все одно O(n).
  • Якщо є вкладений цикл, але він виконується сталу кількість разів (константа), складність залишається O(n).
  • Для різних входів n і m: підсумовуємо - O(n + m).

Приклади алгоритмів O(n)

  • Лінійний пошук у несортованому масиві (найгірший випадок - перегляд усіх елементів).

    js
    function linearSearch(arr, target) { for (let i = 0; i < arr.length; i++) { if (arr[i] === target) return i; // ранній вихід - найкращий випадок O(1) } return -1; // найгірший випадок - O(n) }

  • Підсумовування елементів масиву.

    js
    function sum(arr) { let s = 0; for (const x of arr) s += x; // один прохід return s; // O(n) }

  • Пошук максимуму.

    js
    function max(arr) { if (arr.length === 0) return undefined; let m = arr[0]; for (let i = 1; i < arr.length; i++) { if (arr[i] > m) m = arr[i]; } return m; // O(n) }

  • Підрахунок унікальних значень через Set - час O(n), пам'ять O(n).

    js
    function uniqueCount(arr) { const set = new Set(); for (const x of arr) set.add(x); return set.size; // Час: O(n), Пам'ять: O(n) }

Кілька проходів - все ще O(n)

Два послідовні лінійні проходи підсумовуються і залишаються лінійними.

js
function twoPasses(arr) { for (const x of arr) {/* ... */} // O(n) for (const x of arr) {/* ... */} // O(n) // Разом: O(n + n) = O(n) }

Вкладений цикл зі сталою - теж O(n)

js
for (const x of arr) { for (let k = 0; k < 10; k++) { // 10 - константа, не залежить від n } } // Складність: 10 * n => O(n)

Два різні входи - O(n + m)

js
function merge(a, b) { const res = []; for (const x of a) res.push(x); // O(n) for (const y of b) res.push(y); // O(m) return res; // O(n + m) }

Складності поруч для порівняння

  • O(1) - константна: час не залежить від n.
  • O(log n) - логарифмічна: кожен крок зменшує задачу в кілька разів (бінарний пошук).
  • O(n log n) - наприклад, ефективні сортування (MergeSort, QuickSort у середньому).
  • O(n^2) - вкладені цикли по n (порівняння кожної пари елементів).

Як швидко оцінювати лінійність

  1. Визначте розмір входу n (кількість елементів, довжина рядка тощо).
  2. Порахуйте, скільки разів ви звертаєтеся до кожного елемента - не більше сталого числа разів? Тоді, найімовірніше, O(n).
  3. Складіть незалежні частини і відкиньте константи: O(n) + O(n/2) + O(100) → O(n).
  4. Враховуйте випадки: найкращий/середній/найгірший. Лінійний пошук: найкращий - O(1), найгірший - O(n).
  5. Перевірте пам'ять: якщо зберігаєте структуру, що зростає пропорційно n, то за пам'яттю це O(n).

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

  • Вкладений цикл не завжди дає O(n^2): якщо внутрішній обмежений константою, підсумок - O(n).

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

    js
    function badAppend(items) { let res = []; for (const x of items) { res = [...res, x]; // щоразу копіюємо весь res → O(len) } return res; // Разом O(n^2) } function goodAppend(items) { const res = []; for (const x of items) res.push(x); // амортизовано O(1) return res; // Разом O(n) }

  • Два виклики map/filter поспіль - все ще O(n). Об'єднання в один прохід знижує константи, але не змінює O-нотацію.

  • Ранній вихід покращує найкращий/середній випадок, але асимптотика за найгіршим залишається O(n).

Інтуїція: подвоїли кількість даних - час приблизно подвоївся. Це і є лінійність.

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

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

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

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