Born–Infeld model: Difference between revisions
en>Saehry m Moved to subcategory of physics |
en>Gisling |
||
| Line 1: | Line 1: | ||
In [[computational complexity theory]], '''asymptotic computational complexity''' is the usage of the [[asymptotic analysis]] for the estimation of computational complexity of [[algorithm]]s and [[computational problem]]s, commonly associated with the usage of the [[big O notation]]. | |||
In terms of the most commonly estimated [[computational resource]]s, it is spoken about the '''asymptotic [[time complexity]]''' and '''asymptotic [[space complexity]].''' Other asymptotically estimated resources include [[circuit complexity]] and various measures of [[parallel computation]], such as the number of (parallel) processors. | |||
Since the ground-laying 1965 paper of [[Juris Hartmanis|Hartmanis]] and [[Richard Stearns (computer scientist)|Stearns]]<ref>{{cite doi|10.1090/S0002-9947-1965-0170805-7}}</ref> and the 1979 book by Garey and Johnson on [[NP-completeness]], <ref>[[Michael Garey]], and [[David S. Johnson]]: ''Computers and Intractability: A Guide to the Theory of NP-Completeness.'' New York: W. H. Freeman & Co., 1979.</ref> the term "[[computational complexity]]" (of algorithms) most commonly refers to the asymptotic computational complexity. | |||
Further, unless specified otherwise, the term "computational complexity" usually refers to the [[upper bound]] for the asymptotic computational complexity of an algorithm or a problem, which is usually written in terms of the big O notation, e.g.. <math>O(n^3).</math> Other types of (asymptotic) computational complexity estimates are [[lower bound]]s ("[[Big O notation|Big Omega]]" notation; e.g., Ω(''n'')) and asymptotically tight estimates, when the asymptotic upper and lower bounds coincide (written using the "[[big Theta]]"; e.g., Θ(''n'' log ''n'')). | |||
A further tacit assumption is that the [[worst case analysis]] of computational complexity is in question unless stated otherwise. An alternative approach is [[probabilistic analysis of algorithms]]. | |||
In most practical cases [[deterministic algorithm]]s or [[randomized algorithm]]s are discussed, although [[theoretical computer science]] also considers [[nondeterministic algorithm]]s and other advanced [[models of computation]]. | |||
==See also== | |||
*[[Asymptotically optimal algorithm]] | |||
==References== | |||
{{reflist}} | |||
[[Category:Computational complexity theory]] | |||
Revision as of 07:31, 4 January 2014
In computational complexity theory, asymptotic computational complexity is the usage of the asymptotic analysis for the estimation of computational complexity of algorithms and computational problems, commonly associated with the usage of the big O notation.
In terms of the most commonly estimated computational resources, it is spoken about the asymptotic time complexity and asymptotic space complexity. Other asymptotically estimated resources include circuit complexity and various measures of parallel computation, such as the number of (parallel) processors.
Since the ground-laying 1965 paper of Hartmanis and Stearns[1] and the 1979 book by Garey and Johnson on NP-completeness, [2] the term "computational complexity" (of algorithms) most commonly refers to the asymptotic computational complexity.
Further, unless specified otherwise, the term "computational complexity" usually refers to the upper bound for the asymptotic computational complexity of an algorithm or a problem, which is usually written in terms of the big O notation, e.g.. Other types of (asymptotic) computational complexity estimates are lower bounds ("Big Omega" notation; e.g., Ω(n)) and asymptotically tight estimates, when the asymptotic upper and lower bounds coincide (written using the "big Theta"; e.g., Θ(n log n)).
A further tacit assumption is that the worst case analysis of computational complexity is in question unless stated otherwise. An alternative approach is probabilistic analysis of algorithms.
In most practical cases deterministic algorithms or randomized algorithms are discussed, although theoretical computer science also considers nondeterministic algorithms and other advanced models of computation.
See also
References
43 year old Petroleum Engineer Harry from Deep River, usually spends time with hobbies and interests like renting movies, property developers in singapore new condominium and vehicle racing. Constantly enjoys going to destinations like Camino Real de Tierra Adentro.
- ↑ Template:Cite doi
- ↑ Michael Garey, and David S. Johnson: Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W. H. Freeman & Co., 1979.