Запропонувати правкуПокращити цю статтюДопрацюйте відповідь до «Що таке "швидкість зростання функції"?». Ваші зміни проходять модерацію перед публікацією.Потрібне підтвердженняКонтентЩо ви змінюєте🇺🇸EN🇺🇦UAПереглядЗаголовок (UA)Коротка відповідь (UA)**Швидкість зростання функції** - це те, наскільки швидко збільшується значення f(n) зі зростанням n. В аналізі алгоритмів її описують асимптотичними позначеннями (O, Θ, Ω), щоб порівнювати алгоритми за порядком зростання часу чи пам'яті на великих входах, ігноруючи константи і молодші члени. **Ключове:** константні множники і доданки молодших порядків при n → ∞ ігноруються - важливий лише домінантний член.Показується над повною відповіддю для швидкого нагадування.Відповідь (UA)Зображення## Коротка відповідь Швидкість зростання функції - це те, наскільки швидко збільшується значення 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 → ∞ ігноруються. ### Як порівнювати дві функції на око і формально 1. Метод границь: розгляньте L = lim n->∞ f(n)/g(n). Якщо L = 0, то f ∈ o(g). Якщо 0 < L < ∞, то f ∈ Θ(g). Якщо L = ∞, то f ∈ ω(g). 2. Правила прикидки: поліноміальні степені порівнюємо за показниками; 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) пам'яті.Для рев’юераПримітка для модератора (необов’язково)Бачить лише модератор. Прискорює рев’ю.