Що означає "оцінка за порядком зростання"?

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

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

Оцінка за порядком зростання - це спосіб описати, як час роботи чи обсяг пам'яті алгоритму збільшуються при зростанні розміру входу n. Зазвичай використовується асимптотична нотація O(·): ми відкидаємо константи і молодші члени і залишаємо домінантний внесок, наприклад O(n), O(n log n), O(n²).

Детальне пояснення

Що таке порядок зростання і навіщо він потрібен

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

Зосереджується на домінантному члені: O(n + 5) → O(n).
Ігнорує сталі множники: O(3n) → O(n).

Головна ідея: як змінюється масштаб часу/пам'яті при зростанні n у рази, а не точна кількість операцій.

Основні нотації

O(g(n)) - верхня межа за порядком зростання: алгоритм не гірший, ніж g(n), з точністю до константи при великих n.
Θ(g(n)) - точна за порядком зростання: і верхня, і нижня межі збігаються (асимптотично таке саме зростання).
Ω(g(n)) - нижня межа: алгоритм не кращий, ніж g(n), за порядком зростання.
o(g(n)) - зростає строго повільніше, ніж g(n). ω(g(n)) - зростає строго швидше.
Амортизована складність - середня вартість операції на довгій послідовності викликів (важливо для динамічних структур даних).

Що саме оцінюємо

Час: кількість елементарних кроків (ітерації, порівняння, присвоєння тощо).
Пам'ять: додаткова пам'ять понад вхідні дані (стек рекурсії, тимчасові структури).
Випадок: найгірший (worst-case), середній (average-case), найкращий (best-case). На співбесідах за замовчуванням - найгірший, якщо не обумовлено інше.

Практичні правила оцінки коду

Послідовні ділянки коду: беремо максимум зі складностей, а не суму, якщо вони залежать від однакового n (O(n) + O(n²) → O(n²)).
Один цикл по n елементах → O(n). Кроки циклу з діленням/множенням індексу (i *= 2) → O(log n).
Вкладені незалежні цикли → перемножуємо (зовнішній n, внутрішній n → O(n²)). Послідовні цикли по одному й тому самому масиву → O(n) + O(n) → O(n).
Умовні гілки: беремо максимум з гілок за порядком зростання (найгірший сценарій).
Рекурсія: оцінюємо кількість викликів і роботу на рівень; часто допомагає правило розділяй-і-володарюй (T(n) ≈ a·T(n/b) + f(n)). Приклади: бінарний пошук → O(log n), сортування злиттям → O(n log n).
Визначайте, що таке n: довжина масиву, кількість вузлів у дереві, кількість вершин/ребер у графі тощо. Від цього залежить оцінка.

Приклади коду і їхній порядок зростання (JS)

Лінійний прохід по масиву - O(n) за часом, O(1) за пам'яттю:

function sum(arr) {
  let s = 0;
  for (let i = 0; i < arr.length; i++) {
    s += arr[i];
  }
  return s;
}

Вкладені цикли - O(n²) за часом:

function hasDuplicates(arr) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[i] === arr[j]) return true;
    }
  }
  return false;
}

Бінарний пошук по відсортованому масиву - O(log n) за часом:

function binarySearch(arr, x) {
  let l = 0, r = arr.length - 1;
  while (l <= r) {
    const m = (l + r) >> 1;
    if (arr[m] === x) return m;
    if (arr[m] < x) l = m + 1; else r = m - 1;
  }
  return -1;
}

Злиття двох відсортованих масивів - O(n + m) за часом, O(n + m) за пам'яттю (для результату):

function merge(a, b) {
  const res = [];
  let i = 0, j = 0;
  while (i < a.length && j < b.length) {
    if (a[i] <= b[j]) res.push(a[i++]);
    else res.push(b[j++]);
  }
  while (i < a.length) res.push(a[i++]);
  while (j < b.length) res.push(b[j++]);
  return res;
}

Сортування злиттям - O(n log n) за часом, O(n) додаткової пам'яті:

function mergeSort(arr) {
  if (arr.length <= 1) return arr;
  const mid = arr.length >> 1;
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));
  // Злиття - як у прикладі вище
  const res = [];
  let i = 0, j = 0;
  while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) res.push(left[i++]);
    else res.push(right[j++]);
  }
  while (i < left.length) res.push(left[i++]);
  while (j < right.length) res.push(right[j++]);
  return res;
}

Амортизована складність push у динамічний масив - O(1) у середньому, іноді O(n) при рідкісному розширенні:

class DynArray {
  constructor() {
    this.a = new Array(1);
    this.n = 0;
  }
  push(x) {
    if (this.n === this.a.length) {
      const b = new Array(this.a.length * 2);
      for (let i = 0; i < this.n; i++) b[i] = this.a[i];
      this.a = b; // рідкісна, але дорога операція: O(n)
    }
    this.a[this.n++] = x; // зазвичай O(1)
  }
}

Типові порядки зростання та інтуїція

O(1) - константне: доступ за індексом у масиві, push у кінець динамічного масиву (амортиз.).
O(log n) - ділимо навпіл: бінарний пошук, операції в збалансованих деревах пошуку.
O(n) - лінійний прохід: перевірка умови для кожного елемента масиву/списку/вузла.
O(n log n) - сортування порівняннями, багато алгоритмів divide & conquer (злиття, швидке сортування у середньому).
O(n²) - подвійні вкладені цикли: порівняння всіх з усіма, наївні алгоритми динаміки без оптимізацій.
O(2^n), O(n!) - повний перебір, комбінаторні задачі без оптимізацій/відсічень.

Часті помилки і тонкощі

Плутанина у визначенні n: для графів важливо розрізняти |V| (вершини) і |E| (ребра); для рядків - довжину в символах; для чисел - кількість бітів, а не величину числа.
Ігнорування пам'яті: рекурсивні алгоритми часто потребують O(depth) стека; деякі методи сортування потребують O(n) додаткової пам'яті.
Занадто буквальне сприйняття констант: асимптотика ігнорує константи, але на малих n вони можуть бути важливі на практиці. На співбесіді - обговорюйте компроміси.

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

Скажіть, що вважаєте за n (розмір входу) і який випадок розглядаєте (зазвичай найгірший).
Розберіть код на блоки: послідовні частини, цикли, розгалуження, рекурсія; застосуйте правила додавання/множення/максимуму.
Назвіть часову і просторову складність; за потреби - амортизовану.
Порівняйте альтернативи і вкажіть вузьке місце (наприклад, «вузьке місце - вкладений цикл O(n²)»).

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

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

Premium

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