Складність алгоритмів: кількість операцій, O(n), O(log n), O(n²)
Складність алгоритму
Нас цікавить не секунди на певному комп’ютері, а те, як швидко зростає кількість операцій із збільшенням n.
Типові класи
Запис | Назва | Приклад | n = 1000 |
|---|---|---|---|
O(1) | константна | доступ до | 1 |
O(log n) | логарифмічна | двійковий пошук | ≈ 10 |
O(n) | лінійна | лінійний пошук, сума | 1000 |
O(n log n) | вбудоване сортування | ≈ 10 000 | |
O(n²) | квадратична | бульбашка, вибір, вставки | 1 000 000 |
Що це означає на практиці
Якщо дані збільшити вдесятеро:
O(n) — у 10 разів довше;
O(n²) — у 100 разів довше;
O(log n) — майже нічого.
Просторова складність
Окрім часу, алгоритм потребує пам’яті. Іноді можна «купити» швидкість за пам’ять (наприклад, словник для швидкого пошуку).
Емулятор
У лабораторії нижче порівняйте кількість операцій для різних алгоритмів і подивіться, як вони ростуть із n (також у логарифмічному масштабі).
Перевірте себе
У скільки разів зросте кількість операцій O(n²) при збільшенні n у 3 рази?
Чому двійковий пошук швидший за лінійний?
Для яких n різниця між O(n) і O(n²) непомітна?
BitMath · https://bitmath.com.ua/informatyka/informatyka-8-tema-7/i8-skladnist