Асимптотически оптимальный алгоритм

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

Более формально, алгоритм является асимптотически оптимальным по отношению к конкретному ресурсу , если доказано, что для задачи требуется Ω( f ( n )) этого ресурса, и доказано, что алгоритм использует только O ( f ( n )).

Эти доказательства требуют предположения о конкретной модели вычислений , т. е. определенных ограничений на операции, допустимые с входными данными.

В качестве простого примера известно, что все виды сравнения требуют как минимум Ω( n log n ) сравнений в среднем и наихудшем случаях. Сортировка слиянием и пирамидальная сортировка — это виды сравнения, которые выполняют сравнения O( n log n ) , поэтому они асимптотически оптимальны в этом смысле.

Если входные данные обладают некоторыми априорными свойствами, которые можно использовать при построении алгоритмов, помимо сравнений, тогда возможны асимптотически более быстрые алгоритмы. Например, если известно, что N объектов являются целыми числами из диапазона [1, N ], то их можно отсортировать за время O( N ) , например, с помощью сортировки по корзине .

Следствием того, что алгоритм асимптотически оптимален, является то, что при достаточно больших входных данных ни один алгоритм не может превзойти его более чем в постоянный коэффициент. По этой причине асимптотически оптимальные алгоритмы часто рассматриваются как «конец линии» в исследованиях, достижение результата, который невозможно значительно улучшить. И наоборот, если алгоритм не является асимптотически оптимальным, это означает, что по мере увеличения размера входных данных алгоритм работает все хуже, чем лучший из возможных алгоритмов.

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

Хотя асимптотически оптимальные алгоритмы являются важными теоретическими результатами, асимптотически оптимальный алгоритм не может использоваться в ряде практических ситуаций:

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

Примером асимптотически оптимального алгоритма, не используемого на практике, является алгоритм Бернара Шазеля с линейным временем для триангуляции простого многоугольника . Другой пример — структура данных массива изменяемого размера , опубликованная в книге «Массивы изменяемого размера в оптимальном времени и пространстве». который может индексироваться за постоянное время, но на многих машинах влечет за собой серьезные практические потери по сравнению с обычным индексированием массива.

Формальные определения

Формально предположим, что у нас есть теорема о нижней границе, показывающая, что для решения проблемы требуется время Ω(f( n )) для экземпляра (входных данных) размера n (см. обозначение Big O § обозначение Big Omega для определения Ω). . Тогда алгоритм, который решает задачу за время O(f( n )) называется асимптотически оптимальным. Это также можно выразить с помощью ограничений: предположим, что b( n ) — нижняя граница времени работы, а данный алгоритм требует времени t( n ). Тогда алгоритм асимптотически оптимален, если:

$\lim _{n\rightarrow \infty }{\frac {t(n)}{b(n)}}<\infty .$

Этот предел, если он существует, всегда равен 1, поскольку t( n ) ≥ b( n ).

Хотя алгоритм обычно применяется к эффективности использования времени, можно сказать, что он использует асимптотически оптимальное пространство, случайные биты, количество процессоров или любой другой ресурс, обычно измеряемый с использованием нотации big-O.

Иногда расплывчатые или неявные предположения могут сделать неясным, является ли алгоритм асимптотически оптимальным. Например, теорема о нижней оценке может предполагать конкретную модель абстрактной машины , как в случае с сортировкой сравнения, или конкретную организацию памяти. Нарушая эти предположения, новый алгоритм потенциально может асимптотически превзойти нижнюю границу и «асимптотически оптимальные» алгоритмы.

Ускорение

Отсутствие асимптотически оптимального алгоритма называется ускорением. Теорема Блюма об ускорении показывает, что существуют искусственно созданные проблемы с ускорением. Однако остается открытым вопрос о том , являются ли многие из наиболее известных сегодня алгоритмов асимптотически оптимальными, . Например, существует $O(n\alpha (n))$ алгоритм поиска минимальных остовных деревьев , где $\alpha (n)$ является очень медленно растущей обратной функцией Аккермана , но наиболее известной нижней границей является тривиальная $\Omega (n)$. Неизвестно, является ли этот алгоритм асимптотически оптимальным, и, если бы он был решен в любом случае, он, вероятно, был бы воспринят как важный результат. Копперсмит и Виноград (1982) доказали, что умножение матриц имеет слабую форму ускорения среди ограниченного класса алгоритмов (билинейные тождества типа Штрассена с лямбда-вычислением).

См. также

• Проблема уникальности элемента
• Асимптотическая вычислительная сложность