Оцінювання складності при застосуванні стратегій розроблення алгоритмів

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

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

📖 Головне

• Обчислювальна складність — це залежність кількості елементарних операцій (або обсягу памʼяті) від розміру входу n. Розрізняють часову й просторову складність.

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

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

• Повний перебір (brute force): перебирають усі варіанти. Часто дає O(2ⁿ) або O(n!) — надійно, але повільно.

• Розділяй і володарюй: задачу ділять на підзадачі, розвʼязують їх і обʼєднують. Сортування злиттям і швидке сортування — O(n·log n); двійковий пошук — O(log n).

• Жадібний метод: на кожному кроці беруть локально найкращий варіант. Зазвичай швидкий (часто O(n·log n) або O(n)), але не завжди дає оптимум.

• Динамічне програмування: зберігають розвʼязки підзадач, щоб не рахувати їх двічі. Перетворює експоненту на поліном (напр., числа Фібоначчі: з O(2ⁿ) рекурсії до O(n)).

• Оцінюють найгірший випадок (worst case) — верхню межу; іноді середній і найкращий.

• Вкладені цикли множать складність: один цикл по n — O(n), два вкладені — O(n²).

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

Пошук елемента у відсортованому масиві з n = 1000:

• Лінійний пошук — перебір підряд, у гіршому разі 1000 порівнянь → O(n).

• Двійковий пошук (розділяй і володарюй) — щоразу відкидаємо половину: 1000 → 500 → 250 → … ≈ log₂1000 ≈ 10 порівнянь → O(log n).

Висновок: зміна стратегії зменшила роботу з 1000 до ~10 операцій.

Числа Фібоначчі:

• Наївна рекурсія F(n)=F(n−1)+F(n−2) повторно рахує ті самі значення → O(2ⁿ).

• Динамічне програмування зберігає вже обчислені F → O(n). Для n = 40 це різниця між ~мільярдом і 40 операціями.

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

• Залишають сталі й коефіцієнти: пишуть O(2n) або O(n²+n) замість O(n) і O(n²).

• Плутають вкладені й послідовні цикли: два окремі цикли — це O(n)+O(n)=O(n), а вкладені — O(n²).

• Вважають, що жадібний метод завжди дає оптимальний результат — ні, лише для певних задач.

• Думають, що «розділяй і володарюй» завжди швидше за перебір — обʼєднання підзадач теж має ціну.

• Плутають часову і просторову складність: динамічне програмування зменшує час, але часто витрачає більше памʼяті.

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

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

• Двійковий пошук — O(log n); якісні сортування — O(n·log n); вкладені цикли — O(n²).

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

• Чотири стратегії: перебір, розділяй і володарюй, жадібний, динамічне програмування.

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

1. Яка складність у O-нотації для 5n² + 100n + 3?

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

3. Яка стратегія перетворює рекурсію Фібоначчі з O(2ⁿ) на O(n)?

4. Один цикл по n усередині іншого циклу по n — яка складність?

Відповіді: 1 — O(n²); 2 — O(log n); 3 — динамічне програмування; 4 — O(n²).