Asymptotically optimal

From Wikipedia, the free encyclopedia

You have new messages (last change).

In computer science, an algorithm is said to be asymptotically optimal if, roughly speaking, for large inputs it performs at worst a constant factor 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.

As a simple example, it's known that all comparison sorts require Ω(n log n) time. Mergesort and heapsort are comparison sorts which operate in O(n log n) time, so they are asymptotically optimal in this sense (although there are sorting algorithms with better asymptotic performance, they are necessarily not comparison sorts).

A consequence of an algorithm being asymptotically optimal is that, for large enough inputs, no algorithm can outperform it by more than a fixed constant factor, such as 30%. 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 proved upon. Conversely, if an algorithm is not asymptotically optimal, this implies that as the input grows in size, the algorithm performs more and more times worse than the best possible algorithm.

On the other hand, in practice it's quite useful to find algorithms that perform many times faster, even if they do not enjoy any asymptotic advantage. New algorithms may also present other advantages such as better performance on small inputs, decreased use of other 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 usually important theoretical results, an asymptotically optimal algorithm may not be used in practice for a number of reasons:

  • It only outperforms more commonly-used methods for n beyond the range of practical input sizes, such as inputs with 101000 bits.
  • It is too complex, so that the difficulty of comprehending and implementing it outweighs its potential benefit in the range of input sizes under consideration.
  • Most practical instances fall into special cases that have more efficient algorithms or that heuristic algorithms with bad worst-case times can nevertheless solve efficiently.

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.

[edit] Formal definitions

Formally, suppose that we have a lower-bound theorem showing that a problem requires Ω(f(n)) time to solve for an instance (input) of size n (see big-O notation for the definition of Ω). Then, an algorithm which solves the problem in O(f(n)) time is said to be asymptotically optimal. This can also be expressed using limits: suppose that b(n) is a lower bound on the running time, and a given algorithm takes time t(n). Then the algorithm is asymptotically optimal if:

\lim_{n\rightarrow\infty} \frac{t(n)}{b(n)} < \infty

Note that this limit, if it exists, is always at least 1, as t(n) ≥ b(n).

Although usually applied to time efficiency, an algorithm can be said to use asymptotically optimal space, random bits, number of processors, or any other resource commonly measured using big-O notation.

Sometimes vague or implicit assumptions can make it unclear whether an algorithm is asymptotically optimal. For example, a lower bound theorem might assume a particular abstract machine model, as in the case of comparison sorts, or a particular organization of memory. By violating these assumptions, a new algorithm could potentially asymptotically outperform the lower bound and the "asymptotically optimal" algorithms.

[edit] Unknown optimality

In some cases, we may not know whether an algorithm is asymptotically optimal. We can only be certain that an algorithm is asymptotically optimal when we have proven a lower bound that matches its upper-bound performance. Conversely, we can only be certain that an algorithm is not asymptotically optimal when we have devised an algorithm that is asymptotically faster. Whenever we have an algorithm that is the asymptotically fastest known algorithm for a problem, but with no matching lower bound, we do not know whether it is asymptotically optimal.

For this reason, it is an open problem whether many of the most well-known algorithms today are asymptotically optimal or not. For example, there is an O(nα(n)) algorithm for finding minimum spanning trees, where α(n) is the very slowly-growing inverse of the Ackermann function, but the best known lower bound is the trivial Ω(n). Whether this algorithm is asymptotically optimal is unknown, and would be likely to be hailed as a significant result if it were resolved either way.

Retrieved from "http://en.wikipedia.org../../../a/s/y/Asymptotically_optimal.html"