Асимптотически оптимальный алгоритм - Asymptotically optimal algorithm
В информатике , алгоритм называется асимптотически оптимальным , если, грубо говоря, для больших входов выполняет в худшем случае коэффициент постоянной (независимо от размера входных данных) хуже , чем лучший возможный алгоритм. Это термин часто встречается в информатике исследования в результате широкого использования большого O нотации .
Более формально, алгоритм является асимптотически оптимальным по отношению к конкретному ресурсу, если доказано, что проблема требует Ω (f (n)) этого ресурса, и доказано, что алгоритм использует только O (f (n)).
Эти доказательства требуют предположения о конкретной модели вычислений , т. Е. Определенных ограничений на операции, допустимые с входными данными.
В качестве простого примера известно, что все виды сравнения требуют как минимум Ω ( n log n ) сравнений в среднем и худшем случаях. Mergesort и heapsort - это сортировки сравнения, которые выполняют O ( n log n ) сравнений, поэтому они являются асимптотически оптимальными в этом смысле.
Если входные данные обладают некоторыми априорными свойствами, которые могут быть использованы при построении алгоритмов, помимо сравнений, тогда возможны асимптотически более быстрые алгоритмы. Например, если известно, что N объектов являются целыми числами из диапазона [1, N], то они могут быть отсортированы O (N) раз, например, сортировкой по корзине .
Следствием того, что алгоритм является асимптотически оптимальным, является то, что при достаточно больших входных данных ни один алгоритм не может превзойти его более чем в постоянный коэффициент. По этой причине асимптотически оптимальные алгоритмы часто рассматриваются как «конец линии» в исследованиях, достижение результата, который не может быть значительно улучшен. И наоборот, если алгоритм не является асимптотически оптимальным, это означает, что по мере увеличения размера входных данных алгоритм работает все хуже, чем лучший из возможных алгоритмов.
На практике полезно найти алгоритмы, которые работают лучше, даже если они не имеют асимптотического преимущества. Новые алгоритмы также могут иметь такие преимущества, как лучшая производительность на определенных входных данных, меньшее использование ресурсов или простота описания и реализации. Таким образом, асимптотически оптимальные алгоритмы не всегда являются «концом линии».
Хотя асимптотически оптимальные алгоритмы являются важными теоретическими результатами, асимптотически оптимальный алгоритм может не использоваться в ряде практических ситуаций:
- Он превосходит только более часто используемые методы для n за пределами диапазона практических размеров входных данных, таких как входы с большим количеством битов, чем может поместиться в любой компьютерной системе хранения.
- Он слишком сложен, поэтому сложность его понимания и правильной реализации перевешивает его потенциальную выгоду в рассматриваемом диапазоне размеров входных данных.
- Входные данные, встречающиеся на практике, попадают в особые случаи, когда используются более эффективные алгоритмы или эвристические алгоритмы с плохим временем наихудшего случая, тем не менее, могут эффективно решать.
- На современных компьютерах оптимизация оборудования, такая как кэш памяти и параллельная обработка, может быть «нарушена» асимптотически оптимальным алгоритмом (при условии, что анализ не принимает во внимание эти оптимизации оборудования). В этом случае могут быть неоптимальные алгоритмы, которые лучше используют эти функции и превосходят оптимальный алгоритм на реалистичных данных.
Пример асимптотический оптимальный алгоритм не используется на практике Бернард Чазел линейное время алгоритм «s для триангуляции в виде простого многоугольника . Другой пример - это структура данных массива с изменяемым размером, опубликованная в «Массивах с изменяемым размером в оптимальном времени и пространстве», которая может индексировать в постоянное время, но на многих машинах влечет за собой серьезные практические потери по сравнению с обычным индексированием массивов.
Формальные определения
Формально предположим, что у нас есть теорема о нижней границе, показывающая, что для решения проблемы требуется время Ω (f ( n )) для экземпляра (входа) размера n (см. Определение Ω в обозначении big-O ). Тогда алгоритм, решающий задачу за время O (f ( n )), называется асимптотически оптимальным. Это также можно выразить с помощью пределов: предположим, что b ( n ) - это нижняя граница времени выполнения, а данный алгоритм требует времени t ( n ). Тогда алгоритм будет асимптотически оптимальным, если:
Обратите внимание, что этот предел, если он существует, всегда равен не менее 1, поскольку t ( n ) ≥ b ( n ).
Хотя алгоритм обычно применяется к эффективности времени, можно сказать, что алгоритм использует асимптотически оптимальное пространство, случайные биты, количество процессоров или любой другой ресурс, обычно измеряемый с использованием нотации большого O.
Иногда расплывчатые или неявные предположения могут сделать неясным, является ли алгоритм асимптотически оптимальным. Например, теорема о нижней границе может предполагать конкретную модель абстрактной машины , как в случае сортировок сравнения, или конкретную организацию памяти. Нарушая эти предположения, новый алгоритм потенциально может асимптотически превзойти нижнюю границу и «асимптотически оптимальные» алгоритмы.
Ускорение
Отсутствие асимптотически оптимального алгоритма называется ускорением. Теорема Блюма об ускорении показывает, что существуют искусственно построенные задачи с ускорением. Однако вопрос о том, являются ли многие из наиболее известных сегодня алгоритмов асимптотически оптимальными, остается открытым . Например, существует алгоритм O ( n α ( n )) для поиска минимальных остовных деревьев , где α ( n ) - очень медленно растущая обратная функция Аккермана , но наиболее известной нижней границей является тривиальная оценка Ω ( n ) . Является ли этот алгоритм асимптотически оптимальным, неизвестно, и, вероятно, он был бы воспринят как важный результат, если бы он был разрешен в любом случае. Копперсмит и Виноград (1982) доказали, что умножение матриц имеет слабую форму ускорения среди ограниченного класса алгоритмов (билинейные тождества типа Штрассена с лямбда-вычислением).