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