Сложность алгоритмов: Big-O
Как растёт число операций с размером данных. Сравните классы сложности на графике и посмотрите, сколько шагов выйдет при выбранном n. Считается прямо в браузере.
| Класс | Название | Операций при n=16 |
|---|---|---|
| O(1) | постоянная | 1 |
| O(log n) | логарифмическая | 4 |
| O(n) | линейная | 16 |
| O(n·log n) | линейно-логарифмическая | 64 |
| O(n²) | квадратичная | 256 |
| O(2ⁿ) | экспоненциальная | 65 536 |
| O(n!) | факториальная | 20 922 789 888 000 |
Что такое Big-O
«O-большое» описывает, как растёт время работы (число операций) при увеличении размера входных данных n, отбрасывая константы. Это позволяет сравнивать алгоритмы независимо от компьютера. O(1) — постоянное время, O(log n) — двоичный поиск, O(n) — линейный проход, O(n·log n) — хорошие сортировки, O(n²) — вложенные циклы, O(2ⁿ) и O(n!) — перебор, который быстро становится неподъёмным.
