Запропонувати правкуПокращити цю статтюДопрацюйте відповідь до «Що означає O(n) - лінійна складність?». Ваші зміни проходять модерацію перед публікацією.Потрібне підтвердженняКонтентЩо ви змінюєте🇺🇸EN🇺🇦UAПереглядЗаголовок (UA)Коротка відповідь (UA)**O(n)** - лінійна складність: час виконання (чи кількість елементарних операцій) зростає пропорційно розміру входу n. Якщо збільшити n удвічі, час приблизно подвоїться. Це зазвичай відповідає одному повному проходу по даних без вкладених циклів, що залежать від n. **Ключове:** якщо є вкладений цикл, але він виконується сталу кількість разів (константа), складність залишається O(n).Показується над повною відповіддю для швидкого нагадування.Відповідь (UA)Зображення## Коротка відповідь 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). > Інтуїція: подвоїли кількість даних - час приблизно подвоївся. Це і є лінійність.Для рев’юераПримітка для модератора (необов’язково)Бачить лише модератор. Прискорює рев’ю.