Поняття алгоритму; часова та просторова складність

📌 Про що ця тема

Тут перевіряють, чи розумієш ти, що таке алгоритм, які в нього властивості, і як оцінити, наскільки він «важкий» для комп'ютера за часом виконання та витратами пам'яті. Ключове поняття — обчислювальна складність та оцінка O-велике.

📖 Головне

• Алгоритм — це скінченна чітка послідовність дій, що веде від вхідних даних до результату за скінченну кількість кроків.

• Властивості алгоритму: дискретність (поділ на кроки), визначеність (кожен крок однозначний), скінченність (завершується), масовість (працює для класу задач, а не одного випадку), результативність (дає результат).

• Способи запису: словесний, псевдокод, блок-схема, мовою програмування.

• Часова складність — залежність кількості операцій від обсягу вхідних даних n.

• Просторова складність — залежність обсягу використаної пам'яті від n.

• O-велике (асимптотична оцінка) описує поведінку при великих n, відкидаючи сталі й молодші доданки. Напр. 3n²+5n → O(n²).

• Основні класи зростання (від кращого до гіршого): O(1) сталий, O(log n) логарифмічний, O(n) лінійний, O(n log n), O(n²) квадратичний, O(2ⁿ) експоненційний, O(n!) факторіальний.

• O(1) — час не залежить від n (доступ до елемента масиву за індексом).

• O(log n) — на кожному кроці діапазон зменшується вдвічі (двійковий пошук).

• O(n) — один прохід по даних (лінійний пошук, сума елементів).

• O(n²) — вкладений цикл по всіх парах (прості сортування: бульбашкове, вставками).

• Розрізняють найкращий, середній та найгірший випадки; зазвичай оцінюють найгірший.

🔢 Як це працює на прикладі

Приклад 1. Лінійний пошук числа в масиві з n елементів: перебираємо по черзі, у найгіршому разі переглянемо всі n елементів → O(n) за часом, O(1) за пам'яттю (додаткових структур не створюємо).

Приклад 2. Подвійний вкладений цикл:

for i від 1 до n:

for j від 1 до n:

виконати дію

Внутрішня дія виконується n·n = n² разів → часова складність O(n²). Якщо n=1000, це приблизно мільйон операцій.

Приклад 3. Двійковий пошук у відсортованому масиві: щоразу відкидаємо половину, тому кроків ≈ log₂n. Для n=1024 достатньо 10 кроків → O(log n).

⚠️ Типові помилки

• Плутають часову і просторову складність — це різні ресурси (час vs пам'ять).

• Залишають сталі множники й доданки: пишуть O(2n+3) замість правильного O(n).

• Вважають, що вкладений цикл завжди O(n²) — якщо внутрішній цикл не залежить від n, складність може бути O(n).

• Думають, що O(log n) швидше за O(1) — навпаки, O(1) найшвидший, не залежить від n.

• Ототожнюють кількість рядків коду зі складністю — важлива кількість виконань операцій, а не довжина тексту.

🎯 Що завчити напам'ять

• П'ять властивостей алгоритму: дискретність, визначеність, скінченність, масовість, результативність.

• Порядок класів: O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!).

• Один цикл по n → O(n); два вкладені → O(n²); поділ навпіл → O(log n).

• В O-оцінці відкидаємо сталі та молодші доданки.

🧠 Перевір себе

1. Яка часова складність двійкового пошуку?

2. Назви будь-які три властивості алгоритму.

3. Спрости оцінку: 4n² + 10n + 7.

4. Що швидше при великому n: O(n) чи O(n²)?

Відповіді: 1 — O(log n); 2 — напр. дискретність, скінченність, масовість; 3 — O(n²); 4 — O(n).