2.5 KiB
Executable File
2.5 KiB
Executable File
Это определение асимптотической сложности — того, как растут время или объём памяти при увеличении размера входных данных. Эта оценка используется для подсчета сложности выполнения функций в языках программирования.
Функция временной сложности в некоторых случаях может быть определена точно, но в большинстве своем это бессмысленно. Поэтому входные данные всегда n\ ->\infty.
Время выполнение задачи
Полиномиальное время
Алгоритм типа: O(n^k)
Алгоритмы которые решаются за полиномиальное время. Практически решаемые задачи с реальными данным, сложность.
Характеристики:
- Рост времени - умеренный
- Предсказуемое и стабильное время работы
- Большинство классических алгоритмов работают за это время
- Не требуют перебора всех вариантов
- Можно применять оптимизации, динамическое программирование, жадные стратегии.
Примеры задач:
- Сортировка массива -
O(nlog(n)) - Поиск кратчайшего пути -
O(n+m) - Умножение матриц -
O(n^3) - Проверка простаты - полиномиальный тест
Экспоненциальное время
Алгоритм типа O(k^n),O(n!)
Алгоритмы которые решаются за экспоненциальное время. Такие алгоритмы практически не решаемые с реальными данными.
Характеристики:
- Рост времени - взрывной
- Алгоритм часто основан на полном переборе вариантов
Примеры задач
- Перебор всех подмножеств
O(2^n) - Задача коммивояжера перебором -
O(n!) - Раскрытие графа brut force
- SAT полный перебор