Metraipolis › archive › dc_eea0c015b46d
Asymptotically optimal algorithm — Wikipedia (en)
- Source
- Wikipedia (en)
- Original
- https://en.wikipedia.org/wiki/Asymptotically_optimal_algorithm
- License (as archived)
- CC-BY-SA-4.0
- Archived
- 2026-11-10T05:38:49.655Z
- SHA-256 of the archived text
27aa89ad0465e7f5b00da29ae2691e9c0dc879a9c951bec899013a31c9682410- Stable URL of this page
https://metraipolis.com/documento/dc_eea0c015b46d
How to cite
Asymptotically optimal algorithm — Wikipedia (en) — Wikipedia (en), https://en.wikipedia.org/wiki/Asymptotically_optimal_algorithm (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_eea0c015b46d (Metraipolis archive dc_eea0c015b46d, sha256 27aa89ad0465e7f5b00da29ae2691e9c0dc879a9c951bec899013a31c9682410)
BibTeX
@misc{dceea0c015b46d,
title = {Asymptotically optimal algorithm — Wikipedia (en)},
howpublished = {Wikipedia (en)},
url = {https://en.wikipedia.org/wiki/Asymptotically_optimal_algorithm},
note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_eea0c015b46d; sha256 27aa89ad0465e7f5b00da29ae2691e9c0dc879a9c951bec899013a31c9682410},
year = {2026}
}Archived text
Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (en), https://en.wikipedia.org/wiki/Asymptotically_optimal_algorithm. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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 any 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 that perform O(n log n) comparisons, so they are asymptotically optimal in this sense. If the input data have some a priori properties that 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 (not necessarily distinct) 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 algorithms. 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 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 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 Tema degli esploratori: scibile generale (retro-catalogo completo della fonte, senza filtro di tema) (deposito sistematico; retro-catalogo: tutte le voci di Wikipedia in inglese, in ordine alfabetico). Fonte: Wikipedia in inglese, voce «Asymptotically optimal algorithm» — https://en.wikipedia.org/wiki/Asymptotically_optimal_algorithm Wikidata Q4812191: «algorithm that is at most a constant factor worse than the best possible algorithm for large input sizes» (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q4812191 Autori: i contributori di Wikipedia (cronologia: https://en.wikipedia.org/wiki/Asymptotically_optimal_algorithm?action=history). Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza. Estratto dell'introduzione non modificato nel contenuto; revisione 1324271129, consultata il 2026-11-10T05:35:44.170Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 81c4644a3369633afdb38f0da59b2a5f47910449178d7ca25dbcf34a91e34112