Вычислительная сложность

Сложность вычислительных процессов - это понятие теории сложности вычислений, оценка ресурсов (обычно времени) необходимых для выполнения алгоритма.

Определение

Пусть А - алгоритм решения некоторого класса задач, а N - размерность отдельной задачи этого класса. N может быть, например, размерностью обрабатываемого массива, числом вершин обрабатываемого графа т.д., Обозначим f_ {A} \ left (N \ right) функцию, дает верхний предел максимального числа основных операций (сложение, умножение и т. д.), которые должен выполнить алгоритм А, решая задачу размерности N . Будем говорить, что алгоритм А полиномиальный, если f_ {A} \ left (N \ right) растет не быстрее, чем некоторое полином от N . Иначе А - экспоненциальный алгоритм.

Оказывается, что между этими классами алгоритмов есть существенная разница: при больших размерностях задач (которые, как правило, самые интересные на практике), полиномиальные алгоритмы могут быть выполнены на современных компьютерах, тогда как экспоненциальные алгоритмы для практических размерностей задач, как правило, не могут исполниться полностью. Обычно решения задач, порождающих экспоненциальные алгоритмы, связанный с полным перебором всех возможных вариантов, и ввиду практической невозможности реализации такой стратегии, для их решения разрабатываются другие подходы.

Например, если даже существует экспоненциальный алгоритм для нахождения оптимального решения некоторой задачи, то на практике применяются другие, более эффективные полиномиальные алгоритмы для нахождения не обязательно оптимального, а лишь приемлемого решения (приближенного к оптимальному). Но даже если задача допускает решение с помощью полиномиального алгоритма, его можно построить только после глубокого вникания в суть поставленной задачи.

Полиномиальные алгоритмы также могут существенно различаться в зависимости от степени полинома, аппроксимирующего зависимость f_ {A} \ left (N \ right) . Рассмотрим оценки временной сложности алгоритма. Такая оценка проводится с применением отношения O ("Большое О"): говорят, что f_ {A} \ left (N \ right) растет как g \ left (N \ right) для больших N и записывается это как f_ {A} \ left (N \ right) = O \ left (g \ left (N \ right) \ right) . Если существует положительная константа Const> 0, такая, что \ Lim_ {N \ to \ infty} f_A (N) / g (N) = Const , То оценка О (g (N)) называется асимптотической временной сложности алгоритма.

Оценка В (g (N)) для функции f_A \ left (N \ right) применяется, когда точное значение f_A \ left (N \ right) неизвестно, а известно только порядок увеличения времени, затрачиваемого на решение задачи размерностью N с помощью алгоритма А. Точные значения f_A \ left (N \ right) зависят от конкретной реализации, тогда как О (g (N)) является характеристикой самого алгоритма. Например, если временная асимптотическая сложность алгоритма равна O (N ^ 2) (Такой алгоритм называется квадратичным), то при увеличении N при решении задачи увеличивается как квадрат N. Факт экспоненциальной сложности алгоритма в терминах введенной символики можно записать как f_A \ left (N \ right) = O \ left (k ^ N \ right) , Где k - как правило, целое число больше единицы.

Другой вид оценки связан с введением "малого в": говорят, что f_A \ left (N \ right) растет не быстрее g (N) для больших N, записывается f_A \ left (N \ right) = o \ left (g \ left (N \ right) \ right) , Если \ Lim_ {N \ to \ infty} f_A (N) / g (N) = 0 . Например, очевидно, что x ^ 2 = o (x ^ 5), sin (x) = o (x) . Другой пример: алгоритм А есть полиномиальным, если f_A \ left (N \ right) = o \ left (P_k \ left (N \ right) \ right) , Где P k (N) - некоторое полином от N степени k. Так, алгоритм, асимптотическая сложность которого равна о (N log N), относится к полиномиальных.


Примеры асимптотических сложностей

В следующей таблице приведены часто асимптотические сложности с комментариями.

Графики функций приведенных в таблице.
Сложность Комментарий Примеры
O (1) Устойчивое работе независимо от размера задачи Ожидаемое время поиска в хэши
O (log log n) Очень медленный рост необходимого времени Ожидаемое время работы интерполирующего поиска n элементов
O (log n) Логарифмическое роста - удвоение размера задачи увеличивает время работы на постоянную величину Вычисление x n; двоичный поиск в массиве с n элементов
O (n) Линейное роста - удвоение размера задачи удвоит и необходимое время Сложение / вычитание чисел с n цифр линейный поиск в массиве с n элементов
O (n log n) Линеаритмичне роста - удвоение размера задачи увеличит необходимое время не более чем в два раза Сортировка слиянием или кучей n элементов, нижняя граница сортировки сравнением n элементов
O (n ?) Квадратичное роста - удвоение размера задачи раза увеличивает необходимое время Элементарные алгоритмы сортировки
O (n ?) Кубическое роста - удвоение размера задачи увеличивает необходимое время в восемь раз Обычное умножение матриц
O (c n) Экспоненциальный рост - увеличение размера задачи на 1 приводит к c-кратного увеличения необходимого времени; удвоение размера задачи преподносит необходимое время в квадрат Некоторые задачи коммивояжера, алгоритмы поиска полным перебором



Смотрите также


Сигма Это незавершенная статья математики.
Вы можете помочь проекту, исправив и дополнив ее.
Компьютер Это незавершенная статья о компьютеры.
Вы можете помочь проекту, исправив и дополнив ее.