Запропонувати правкуПокращити цю статтюДопрацюйте відповідь до «Що означає "оцінка за порядком зростання"?». Ваші зміни проходять модерацію перед публікацією.Потрібне підтвердженняКонтентЩо ви змінюєте🇺🇸EN🇺🇦UAПереглядЗаголовок (UA)Коротка відповідь (UA)**Оцінка за порядком зростання** - це спосіб описати, як час роботи чи обсяг пам'яті алгоритму збільшуються при зростанні розміру входу n. Зазвичай використовується асимптотична нотація O(·): ми відкидаємо константи і молодші члени і залишаємо домінантний внесок, наприклад O(n), O(n log n), O(n²). **Ключове:** головна ідея - як змінюється масштаб часу/пам'яті при зростанні n у рази, а не точна кількість операцій.Показується над повною відповіддю для швидкого нагадування.Відповідь (UA)Зображення## Коротка відповідь Оцінка за порядком зростання - це спосіб описати, як час роботи чи обсяг пам'яті алгоритму збільшуються при зростанні розміру входу 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 вони можуть бути важливі на практиці. На співбесіді - обговорюйте компроміси. ### Як відповідати на співбесіді 1. Скажіть, що вважаєте за n (розмір входу) і який випадок розглядаєте (зазвичай найгірший). 2. Розберіть код на блоки: послідовні частини, цикли, розгалуження, рекурсія; застосуйте правила додавання/множення/максимуму. 3. Назвіть часову і просторову складність; за потреби - амортизовану. 4. Порівняйте альтернативи і вкажіть вузьке місце (наприклад, «вузьке місце - вкладений цикл O(n²)»).Для рев’юераПримітка для модератора (необов’язково)Бачить лише модератор. Прискорює рев’ю.