Сложность алгоритмов
Интерактивное демо «Сложность алгоритмов» — раздел Энциклопедия · Данные и разметка.
Рост алгоритмической сложности
Двигайте размер входа n и сравните, как растёт число операций у разных классов O
| Класс | Операций при n | Если n × 10 |
|---|---|---|
| O(1) | 1 | ×1.00 |
| O(log n) | 7 | ×1.50 |
| O(n) | 100 | ×10.0 |
| O(n log n) | 664 | ×15.0 |
| O(n²) | 10.0 тыс | ×100 |
Линейная
100
линейный проход по массиву
for (i = 0; i < n; i++) { … }Рост при n → 10n
×10.0
Удвоение данных ≈ удвоение времени; ×10 данных ≈ ×10 времени.
Ось Y на графике — логарифм числа операций, чтобы уместить и O(n), и O(n²) на одном поле. Константы в Big-O отбрасываются: сравниваем темп роста, а не точные миллисекунды.