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

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

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

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

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

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

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

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

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

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

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

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

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

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

Обратите внимание, что этот предел, если он существует, всегда не меньше 1, так как t (п) ≥ b (п).

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

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

Ускорение

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

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

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

Рекомендации

1. Бродник, Андрей; Карлссон, Сванте; Седжвик, Роберт; Munro, JI; Demaine, ED (1999), Массивы с изменяемым размером в оптимальное время и пространство (PDF), Департамент компьютерных наук, Университет Ватерлоо