В информатике алгоритм называется асимптотически оптимальным, если , грубо говоря, для больших входных данных он работает в худшем случае на постоянный фактор (независимо от размера входных данных) хуже, чем наилучший возможный алгоритм. Это термин, который часто встречается в исследованиях в области информатики в результате широкого использования нотации big-O .
Более формально, алгоритм асимптотически оптимален по отношению к конкретному ресурсу, если доказано, что задача требует Ω( f ( n )) этого ресурса, и доказано, что алгоритм использует только O( f ( n )).
Эти доказательства требуют предположения о конкретной модели вычислений , т. е. определенных ограничениях на операции, допустимые с входными данными.
В качестве простого примера, известно, что все сортировки сравнения требуют по крайней мере Ω( n log n ) сравнений в среднем и худшем случаях. Сортировка слиянием и пирамидальная сортировка являются сортировками сравнения, которые выполняют O( n log n ) сравнений, поэтому они асимптотически оптимальны в этом смысле.
Если входные данные имеют некоторые априорные свойства, которые могут быть использованы при построении алгоритмов, в дополнение к сравнениям, то асимптотически более быстрые алгоритмы могут быть возможны. Например, если известно, что N объектов являются целыми числами из диапазона [1, N ], то они могут быть отсортированы за O( N ) времени, например, с помощью сортировки ведром .
Следствием асимптотической оптимальности алгоритма является то, что для достаточно больших входных данных ни один алгоритм не может превзойти его более чем на постоянный множитель. По этой причине асимптотически оптимальные алгоритмы часто рассматриваются как «конец линии» в исследованиях, достижение результата, который не может быть радикально улучшен. И наоборот, если алгоритм не является асимптотически оптимальным, это означает, что по мере увеличения размера входных данных алгоритм работает все хуже, чем наилучший возможный алгоритм.
На практике полезно найти алгоритмы, которые работают лучше, даже если они не обладают никаким асимптотическим преимуществом. Новые алгоритмы также могут иметь такие преимущества, как лучшая производительность на определенных входных данных, меньшее использование ресурсов или простота описания и реализации. Таким образом, асимптотически оптимальные алгоритмы не всегда являются «концом линии».
Хотя асимптотически оптимальные алгоритмы являются важными теоретическими результатами, асимптотически оптимальный алгоритм может не использоваться в ряде практических ситуаций:
Примером асимптотически оптимального алгоритма, не используемого на практике, является линейный алгоритм Бернарда Шазелла для триангуляции простого многоугольника . Другой пример — структура данных массива с изменяемым размером, опубликованная в «Resizable Arrays in Optimal Time and Space», [1] , которая может индексироваться за постоянное время, но на многих машинах имеет большой практический штраф по сравнению с обычной индексацией массива.
Формально предположим, что у нас есть теорема о нижней границе, показывающая, что задача требует времени Ω(f( n )) для решения для экземпляра (входа) размера n (см. нотацию Big O § нотация Big Omega для определения Ω). Тогда алгоритм, который решает задачу за время O(f( n )) называется асимптотически оптимальным. Это также можно выразить с помощью пределов: предположим, что b( n ) является нижней границей времени выполнения, а заданный алгоритм занимает время t( n ). Тогда алгоритм является асимптотически оптимальным, если:
Этот предел, если он существует, всегда не меньше 1, так как t( n ) ≥ b( n ).
Хотя обычно это применяется к эффективности по времени, можно сказать, что алгоритм использует асимптотически оптимальное пространство, случайные биты, количество процессоров или любой другой ресурс, обычно измеряемый с помощью нотации «большое О».
Иногда неясные или неявные предположения могут сделать неясным, является ли алгоритм асимптотически оптимальным. Например, теорема о нижней границе может предполагать определенную абстрактную модель машины , как в случае сравнительных сортировок, или определенную организацию памяти. Нарушая эти предположения, новый алгоритм может потенциально асимптотически превзойти нижнюю границу и «асимптотически оптимальные» алгоритмы.
Несуществование асимптотически оптимального алгоритма называется ускорением. Теорема Блюма об ускорении показывает, что существуют искусственно созданные проблемы с ускорением. Однако остается открытым вопрос , являются ли многие из наиболее известных алгоритмов сегодня асимптотически оптимальными или нет. Например, существует алгоритм для поиска минимальных остовных деревьев , где — очень медленно растущая обратная функция Аккермана , но наиболее известная нижняя граница — это тривиальная . Является ли этот алгоритм асимптотически оптимальным, неизвестно, и, вероятно, его можно было бы считать значимым результатом, если бы он был решен любым способом. Копперсмит и Виноград (1982) доказали, что умножение матриц имеет слабую форму ускорения среди ограниченного класса алгоритмов (билинейные тождества типа Штрассена с лямбда-вычислением).
