О-большое (Big O) — это математическая нотация, которая используется для оценки эффективности алгоритмов, а именно того, как быстро увеличивается время выполнения или объем используемой памяти алгоритма при росте размера входных данных
Основные обозначения сложности алгоритмов
| Обозначение | Название | Описание и пример |
|---|---|---|
| O(1) | Константная | Время не зависит от размера входных данных. Пример: доступ к элементу массива по индексу. |
| O(log n) | Логарифмическая | Время растёт медленно, пропорционально логарифму размера входа. Пример: бинарный поиск. |
| O(√n) | Корневая | Время растёт пропорционально корню из размера входа. Пример: перебор делителей числа. |
| O(n) | Линейная | Время растёт прямо пропорционально размеру входа. Пример: проход по массиву. |
| O(n log n) | Линейно-логарифмическая | Быстрее квадратичной, но медленнее линейной. Пример: сортировка слиянием, быстрая сортировка. |
| O(n²) | Квадратичная | Время пропорционально квадрату размера входа. Пример: сортировка пузырьком, вложенные циклы. |
| O(n³) | Кубическая | Время пропорционально кубу размера входа. Пример: три вложенных цикла. |
| O(n^k) | Полиномиальная | Время пропорционально n в степени k. Пример: вложенные циклы, где k — количество циклов. |
| O(2ⁿ) | Экспоненциальная | Время удваивается с каждым увеличением входа. Пример: перебор всех подмножеств. |
| O(n!) | Факториальная | Время растёт очень быстро, перебор всех перестановок. Пример: полный перебор маршрутов. |
| Ω(…) | Омега-большое | Нижняя граница сложности (лучший случай). |
| Θ(…) | Тета-большое | Точная асимптотика (одновременно верхняя и нижняя граница). |