Стрілки або пробіл — перемикання · F — повний екран · T — проєкторна тема · ? — підказка
Нас цікавить не секунди на певному комп’ютері, а те, як швидко зростає кількість операцій із збільшенням 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²) непомітна?