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

Введение

Измерение производительности алгоритма для больших входных данных

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

In computer science, an algorithm is said to be asymptotically optimal if, roughly speaking, for large inputs it performs at worst a constant factor (independent of the input size) worse than the best possible algorithm. It is a term commonly encountered in computer science research as a result of widespread use of big O notation. More formally, an algorithm is asymptotically optimal with respect to a particular resource if the problem has been proven to require Ω(f(n)) of that resource, and the algorithm has been proven to use only O(f(n)). These proofs require an assumption of a particular model of computation, i. e., certain restrictions on operations allowable with the input data. As a simple example, it's known that all comparison sorts require at least Ω(n log n) comparisons in the average and worst cases. Mergesort and heapsort are comparison sorts which perform O(n log n) comparisons, so they are asymptotically optimal in this sense. If the input data have some a priori properties which can be exploited in construction of algorithms, in addition to comparisons, then asymptotically faster algorithms may be possible. For example, if it is known that the N objects are integers from the range [1, N], then they may be sorted O(N) time, e. g., by the bucket sort. A consequence of an algorithm being asymptotically optimal is that, for large enough inputs, no algorithm can outperform it by more than a constant factor. For this reason, asymptotically optimal algorithms are often seen as the "end of the line" in research, the attaining of a result that cannot be dramatically improved upon. Conversely, if an algorithm is not asymptotically optimal, this implies that as the input grows in size, the algorithm performs increasingly worse than the best possible algorithm. In practice it's useful to find algorithms that perform better, even if they do not enjoy any asymptotic advantage. New algorithms may also present advantages such as better performance on specific inputs, decreased use of resources, or being simpler to describe and implement. Thus asymptotically optimal algorithms are not always the "end of the line". Although asymptotically optimal algorithms are important theoretical results, an asymptotically optimal algorithm might not be used in a number of practical situations:
It only outperforms more commonly used methods for n beyond the range of practical input sizes, such as inputs with more bits than could fit in any computer storage system. It is too complex, so that the difficulty of comprehending and implementing it correctly outweighs its potential benefit in the range of input sizes under consideration. The inputs encountered in practice fall into special cases that have more efficient algorithms or that heuristic algorithms with bad worst case times can nevertheless solve efficiently. On modern computers, hardware optimizations such as memory cache and parallel processing may be "broken" by an asymptotically optimal algorithm (assuming the analysis did not take these hardware optimizations into account). In this case, there could be sub optimal algorithms that make better use of these features and outperform an optimal algorithm on realistic data. An example of an asymptotically optimal algorithm not used in practice is Bernard Chazelle's linear time algorithm for triangulation of a simple polygon. Another is the resizable array data structure published in "Resizable Arrays in Optimal Time and Space", which can index in constant time but on many machines carries a heavy practical penalty compared to ordinary array indexing.

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

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

Этот предел, если он существует, всегда больше или равен 1, поскольку t(n) ≥ b(n). Хотя обычно это применяется к временной эффективности, алгоритм может использовать асимптотически оптимальный объем памяти, случайные биты, количество процессоров или любой другой ресурс, обычно измеряемый с использованием нотации «большое O». Иногда нечеткие или подразумеваемые предположения могут затруднить определение того, является ли алгоритм асимптотически оптимальным. Например, теорема о нижней границе может предполагать конкретную абстрактную модель машины, как в случае сортировки сравнением, или конкретную организацию памяти. Нарушая эти предположения, новый алгоритм потенциально может асимптотически превзойти нижнюю границу и «асимптотически оптимальные» алгоритмы.

Ускорение

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