Складність алгоритмів: час, пам’ять, O(n), O(n²)
Навіщо
Два алгоритми дають однакову відповідь, але один працює 1 секунду, а другий — рік. Складність показує, як росте час зі збільшенням обсягу даних n.
Позначення O
O | Назва | Приклад | n = 1000 |
|---|---|---|---|
O(1) | стала | доступ до елемента за індексом | 1 |
O(log n) | логарифмічна | бінарний пошук | 10 |
O(n) | лінійна | пошук максимуму, сума | 1 000 |
O(n log n) | вбудоване сортування | 10 000 | |
O(n²) | квадратична | сортування обміном | 1 000 000 |
O(2ⁿ) | експоненціальна | перебір усіх підмножин | неможливо |
Стала відкидається: 5n і 100n — обидва O(n). Важливий вигляд росту.
Як рахувати
Один цикл по n — O(n).
Цикл у циклі — O(n²).
Цикл, що ділить область навпіл, — O(log n).
Послідовні блоки додаються, береться найбільший.
for i in range(n): # n разів
for j in range(n): # n разів
print(i, j) # O(n²)Експеримент
Відкрийте лабораторію «Складність алгоритмів» нижче: вона порівнює кількість операцій у різних алгоритмів для різних n. Збільшіть n у 10 разів і дивіться, у скільки разів зросло навантаження.
Складність за пам’яттю
Масив на n чисел — O(n) пам’яті. Сортування «на місці» — O(1) додаткової пам’яті.
Перевірте себе
Яка складність пошуку максимуму? Бінарного пошуку?
У скільки разів збільшиться час алгоритму O(n²), якщо n зросте втричі?
Чому сталі множники відкидають?
BitMath · https://bitmath.com.ua/informatyka/informatyka-9-tema-7/i9-skladnist-alhorytmiv