- Сложность выполнения алгоритма оценивается по затраченному времени или занимаемому объёму памяти.
- NP-полная (недетерминированно полиномиальная) задача – это задача из NP-класса, алгоритм решения которой находится за полиномиальное время.
- NP-класс – класс задач, которые проверяются за полиномиальное время.
Сложность | Пояснение | Примеры |
|---|---|---|
Константная O (1) | Время работы не зависит от количества элементов | Поиск элемента по индексу |
Линейная O (n) | Время работы возрастает прямо пропорционально количеству элементов | Перебор элементов массива |
Логарифмическая O (log n) | Удвоение размера задачи увели-чит время работы на константу | Бинарный поиск |
Линеарифметическая | Удвоение размера входных данных увеличит время выполнения чуть более, чем вдвое | Сортировка слиянием, множеством |
Полиномиальная O (nk), | Удвоение размера входных данных увеличивает время выполнения в 4 раза | Алгоритмы простой сортировки |
Экспоненциальная kn,
| Увеличение размера задачи на 1 приводит к k‑кратному увеличе-нию необходимого времени | Алгоритмы перебора |
Факториальная O (n!) | Время работы сильно возрастает даже при небольшом увеличении набора данных | Алгоритмы комбинато-рики |