Що таке "швидкість зростання функції"?

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

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

Швидкість зростання функції - це те, наскільки швидко збільшується значення f(n) зі зростанням n. В аналізі алгоритмів її описують асимптотичними позначеннями (O, Θ, Ω), щоб порівнювати алгоритми за порядком зростання часу чи пам'яті на великих входах, ігноруючи константи і молодші члени.

Детально

Визначення та інтуїція

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

Навіщо це потрібно в алгоритмах

Оцінка масштабованості: як алгоритм поводиться на великих даних.
Порівняння альтернатив: обираємо менший порядок зростання (наприклад, n log n краще, ніж n^2).
Ігнорування несуттєвих факторів: константи і нижчі степені не впливають на асимптотику.

Основні асимптотичні позначення (нотації)

O(g(n)) - верхня оцінка (не зростає швидше, з точністю до константи): f(n) ∈ O(g(n)), якщо ∃ c > 0, n0: f(n) ≤ c·g(n) для всіх n ≥ n0.
Ω(g(n)) - нижня оцінка (не зростає повільніше, з точністю до константи): f(n) ∈ Ω(g(n)), якщо ∃ c > 0, n0: f(n) ≥ c·g(n) для всіх n ≥ n0.
Θ(g(n)) - точний порядок (і верхня, і нижня оцінка одночасно): f(n) ∈ Θ(g(n)), якщо f ∈ O(g) і f ∈ Ω(g).
o(g(n)) - строго повільніше (f/g → 0).
ω(g(n)) - строго швидше (f/g → ∞).

Важливо: основа логарифма не впливає на порядок зростання (log_a n = (log_a b)·log_b n - константа-множник). Константні множники і доданки молодших порядків при n → ∞ ігноруються.

Як порівнювати дві функції на око і формально

Метод границь: розгляньте L = lim n->∞ f(n)/g(n). Якщо L = 0, то f ∈ o(g). Якщо 0 < L < ∞, то f ∈ Θ(g). Якщо L = ∞, то f ∈ ω(g).
Правила прикидки: поліноміальні степені порівнюємо за показниками; n^a << n^b, якщо a < b. Будь-який поліном << експоненти b^n. Логарифми зростають повільніше за лінійні функції: log n << n.

Ієрархія типових порядків зростання (від повільного до швидкого)

Порядок зростання	Короткий коментар/приклад
1 (константна)	Доступ до елемента масиву за індексом
log n	Бінарний пошук
n	Однопрохідна обробка масиву
n log n	Сортування порівняннями (merge/quick у середньому)
n^2	Два вкладені цикли (бульбашкове сортування)
n^3	Три вкладені цикли (наївне множення матриць)
2^n	Повний перебір підмножин/рішень (експонента)
n!	Перебір усіх перестановок (дуже швидко зростає)

Приклади коду, що ілюструють різні швидкості зростання

javascript

// O(1): константний час - не залежить від n
function getFirst(arr) {
  return arr[0];
}

// O(n): лінійний час - один прохід по масиву
function sum(arr) {
  let s = 0;
  for (let i = 0; i < arr.length; i++) {
    s += arr[i];
  }
  return s;
}

// O(n log n): розділяй і володарюй (приклад - сортування злиттям)
function mergeSort(arr) {
  if (arr.length <= 1) return arr;
  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));
  return merge(left, right);
}

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++]);
  }
  return res.concat(a.slice(i)).concat(b.slice(j));
}

// O(n^2): два вкладені цикли - порівняння всіх пар
function hasDuplicateQuadratic(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(n) з хеш-таблицею (менша швидкість зростання)
function hasDuplicateLinear(arr) {
  const seen = new Set();
  for (const x of arr) {
    if (seen.has(x)) return true;
    seen.add(x);
  }
  return false;
}

Практичні поради для співбесід

Говоріть у термінах розміру входу n і використовуйте нотації O/Θ/Ω.
Ігноруйте константи і молодші члени: 3n^2 + 10n + 100 - це Θ(n^2).
Уточнюйте найкращий/середній/найгірший випадки і використовувану модель даних (наприклад, доступ до хеш-таблиці амортизовано).
Розрізняйте теорію і практику: при малих n алгоритм з більшим порядком зростання може бути швидшим через малі константи, але програє при зростанні n.

Типові хибні уявлення і тонкощі

Big-O - це не точний час, а верхня асимптотична межа.
n log n може бути більшим за n^2 при дуже малих n, але асимптотично n log n зростає повільніше.
Представлення входу важливе: числа у двійковому вигляді змінюють вартість операцій логарифмічно.
Асимптотика по пам'яті - теж швидкість зростання: наприклад, структура даних з Θ(n) пам'яті.

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

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

Premium

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