|
|
| Line 1: |
Line 1: |
| {{Redirect|Running time|the film|Running Time (film)}}
| | I am Son from Dieppe. I love to play Mandolin. Other hobbies are Rugby league football.<br><br>My webpage :: [https://www.youtube.com/watch?v=HkusYtVK2Kw Temple Run 2 Cheats] |
| {{Refimprove|date=January 2010}}
| |
| In [[computer science]], the '''time complexity''' of an [[algorithm]] quantifies the amount of time taken by an algorithm to run as a function of the length of the [[String (computer science)|string]] representing the input<ref name=Sipser />{{RP|226}}. The time complexity of an algorithm is commonly expressed using [[big O notation]], which excludes coefficients and lower order terms. When expressed this way, the time complexity is said to be described ''asymptotically'', i.e., as the input size goes to infinity. For example, if the time required by an algorithm on all inputs of size ''n'' is at most {{nowrap|1=5''n''<sup>3</sup> + 3''n''}}, the asymptotic time complexity is O(''n''<sup>3</sup>).
| |
| | |
| Time complexity is commonly estimated by counting the number of elementary operations performed by the algorithm, where an elementary operation takes a fixed amount of time to perform. Thus the amount of time taken and the number of elementary operations performed by the algorithm differ by at most a constant factor.
| |
| | |
| Since an algorithm's performance time may vary with different inputs of the same size, one commonly uses the [[Worst-case complexity|worst-case time complexity]] of an algorithm, denoted as '''''T''(''n'')''', which is defined as the maximum amount of time taken on any input of size ''n''. Time complexities are classified by the nature of the function ''T''(''n''). For instance, an algorithm with ''T''(''n'') = O(''n'') is called a linear time algorithm, and an algorithm with ''T''(''n'') = O(2<sup>''n''</sup>) is said to be an exponential time algorithm.
| |
| | |
| ==Table of common time complexities==
| |
| {{Further|Computational complexity of mathematical operations}}
| |
| The following table summarizes some classes of commonly encountered time complexities. In the table, poly(''x'') = ''x''<sup>''O''(1)</sup>, i.e., polynomial in ''x''.
| |
| | |
| {| class="wikitable"
| |
| |-
| |
| ! Name !! [[Complexity class]] !! Running time (''T''(''n'')) !! Examples of running times !! Example algorithms
| |
| |-
| |
| | constant time || || ''O''(1) || 10 || Determining if an integer (represented in binary) is even or odd
| |
| |-
| |
| | [[inverse Ackermann function|inverse Ackermann]] time || || ''O''(α(n)) || || [[Amortized time]] per operation using a [[disjoint set data structure|disjoint set]]
| |
| |-
| |
| | [[iterated logarithm]]ic time || || ''O''({{log-star}} ''n'') || || [[Cole-Vishkin algorithm|Distributed coloring of cycles]]
| |
| |-
| |
| | log-logarithmic || || ''O''(log log ''n'') || || Amortized time per operation using a bounded [[priority queue]]<ref>{{Cite journal|first1=Kurt |last1=Mehlhorn |first2=Stefan |last2=Naher|year=1990|title=Bounded ordered dictionaries in O(log log N) time and O(n) space|journal=Information Processing Letters|doi=10.1016/0020-0190(90)90022-P|volume=35|issue=4|pages=183}}</ref>
| |
| |-
| |
| | logarithmic time || [[DLOGTIME]] || ''O''(log ''n'') || log ''n'', log(''n''<sup>2</sup>) || [[Binary search]]
| |
| |-
| |
| | polylogarithmic time || || poly(log ''n'') || (log ''n'')<sup>2</sup> ||
| |
| |-
| |
| |fractional power || || ''O''(''n''<sup>c</sup>) where 0 < c < 1 || ''n<sup>1/2</sup>'', ''n<sup>2/3</sup>'' || Searching in a [[kd-tree]]
| |
| |-
| |
| | linear time || || ''O''(''n'') || ''n'' || Finding the smallest item in an unsorted [[Array data structure|array]]
| |
| |-
| |
| | "n log star n" time || || ''O''(''n'' {{log-star}} ''n'') || || [[Raimund Seidel|Seidel]]'s [[polygon triangulation]] algorithm.
| |
| |-
| |
| | linearithmic time || || ''O''(''n'' log ''n'') || ''n'' log ''n'', log ''n''! || Fastest possible [[comparison sort]]
| |
| |-
| |
| | quadratic time || || ''O''(''n''<sup>2</sup>) || ''n''<sup>2</sup> || [[Bubble sort]]; [[Insertion sort]]; [[Convolution theorem|Direct convolution]]
| |
| |-
| |
| | cubic time || || ''O''(''n''<sup>3</sup>) || ''n''<sup>3</sup> || Naive multiplication of two ''n''×''n'' matrices. Calculating [[partial correlation]].
| |
| |-
| |
| | polynomial time || [[P (complexity)|P]] || 2<sup>''O''(log ''n'')</sup> = poly(''n'') || ''n'', ''n'' log ''n'', ''n''<sup>10</sup></sup> || [[Karmarkar's algorithm]] for [[linear programming]]; [[AKS primality test]]
| |
| |-
| |
| | quasi-polynomial time || QP || 2<sup>poly(log ''n'')</sup> || ''n''<sup>log log ''n''</sup>, ''n''<sup>log ''n''</sup> || Best-known O(log<sup>2</sup> ''n'')-[[approximation algorithm]] for the directed [[Steiner tree problem]].
| |
| |-
| |
| | sub-exponential time<br/>(first definition) || SUBEXP || ''O''(2<sup>''n''<sup>''ε''</sup></sup>) for all ''ε'' > 0 || ''O''(2<sup>log ''n''<sup>log log ''n''</sup></sup>) || Assuming complexity theoretic conjectures, [[Bounded-error probabilistic polynomial|BPP]] is contained in SUBEXP.<ref name="bpp" />
| |
| |-
| |
| | sub-exponential time<br/>(second definition) || || 2<sup>''o''(''n'')</sup> || 2<sup>''n''<sup>1/3</sup></sup> || Best-known algorithm for [[integer factorization]] and [[graph isomorphism problem|graph isomorphism]]
| |
| |-
| |
| | exponential time || [[E (complexity)|E]] || 2<sup>''O''(''n'')</sup> || 1.1<sup>''n''</sup>, 10<sup>''n''</sup> || Solving the [[traveling salesman problem]] using [[dynamic programming]]
| |
| |-
| |
| | factorial time || || ''O''(''n''!) || ''n''! || Solving the traveling salesman problem via [[brute-force search]]
| |
| |-
| |
| | exponential time || [[EXPTIME]] || 2<sup>poly(''n'')</sup> || 2<sup>''n''</sup>, 2<sup>''n''<sup>2</sup></sup> ||
| |
| |-
| |
| | double exponential time || [[2-EXPTIME]] || 2<sup>2<sup>poly(''n'')</sup></sup> || 2<sup>2<sup>''n''</sup></sup> || Deciding the truth of a given statement in [[Presburger arithmetic]]
| |
| |}
| |
| | |
| ==Constant time==
| |
| An algorithm is said to be '''constant time''' (also written as '''O(1)''' time) if the value of ''T''(''n'') is bounded by a value that does not depend on the size of the input. For example, accessing any single element in an [[array data structure|array]] takes constant time as only one [[Instruction (computer science)|operation]] has to be performed to locate it. However, finding the minimal value in an unordered array is not a constant time operation as a scan over each [[element (math)|element]] in the array is needed in order to determine the minimal value. Hence it is a linear time operation, taking O(n) time. If the number of elements is known in advance and does not change, however, such an algorithm can still be said to run in constant time.
| |
| | |
| Despite the name "constant time", the running time does not have to be independent of the problem size, but an upper bound for the running time has to be bounded independently of the problem size. For example, the task "exchange the values of ''a'' and ''b'' if necessary so that ''a''≤''b''" is called constant time even though the time may depend on whether or not it is already true that ''a'' ≤ ''b''. However, there is some constant ''t'' such that the time required is always ''at most'' ''t''.
| |
| | |
| Here are some examples of code fragments that run in constant time:
| |
| | |
| int index = 5;
| |
| int item = list[index];
| |
| '''if''' (condition true) '''then'''
| |
| perform some operation that runs in constant time
| |
| '''else'''
| |
| perform some other operation that runs in constant time
| |
| '''for''' i = 1 '''to''' 100
| |
| '''for''' j = 1 '''to''' 200
| |
| perform some operation that runs in constant time
| |
| | |
| If ''T''(''n'') is O(''any constant value''), this is equivalent to and stated in standard notation as ''T''(''n'') being O(1).
| |
| | |
| ==Logarithmic time==
| |
| {{Further|Logarithmic growth}}
| |
| An algorithm is said to take '''logarithmic time''' if ''T''(''n'') = '''O(log ''n'')'''. Due to the use of the [[binary numeral system]] by computers, the [[logarithm]] is frequently base 2 (that is, log<sub>2</sub> ''n'', sometimes written lg ''n''). However, by the [[Logarithmic identities#Changing the base|change of base]] equation for logarithms, log<sub>a</sub> ''n'' and log<sub>b</sub> ''n'' differ only by a constant multiplier, which in big-O notation is discarded; thus O(log ''n'') is the standard notation for logarithmic time algorithms regardless of the base of the logarithm.
| |
| | |
| Algorithms taking logarithmic time are commonly found in operations on [[binary tree]]s or when using [[binary search]].
| |
| | |
| An O(log n) algorithm is considered highly efficient, as the operations per instance required to complete decrease with each instance.
| |
| | |
| A very simple example of this type of f(n) is an algorithm that cuts a string in half. It will take O(log n) time (n being the length of the string) since we chop the string in half before each print (we make the assumption that ''console.log'' and ''str.substring'' run in constant time).
| |
| This means, in order to increase the number of prints, we have to double the length of the string.
| |
| | |
| <syntaxhighlight lang="javascript">
| |
| // Function to recursively print the right half of a string
| |
| var right = function(str){
| |
| var length = str.length;
| |
|
| |
| // Helper function
| |
| var help = function(index){
| |
|
| |
| // Recursive Case: Print right half
| |
| if(index < length){
| |
|
| |
| // Prints characters from index until the end of the array
| |
| console.log(str.substring(index, length));
| |
|
| |
| // Recursive Call: call help on right half
| |
| help(Math.ceil((length + index)/2));
| |
| }
| |
|
| |
| // Base Case: Do Nothing
| |
| }
| |
| help(0);
| |
| }
| |
| </syntaxhighlight>
| |
| | |
| ==Polylogarithmic time==
| |
| An algorithm is said to run in '''polylogarithmic time''' if ''T''(''n'') = O((log ''n'')<sup>''k''</sup>), for some constant ''k''. For example, matrix chain ordering can be solved in polylogarithmic time on a [[Parallel Random Access Machine]].<ref>{{Cite journal| last1=Bradford | first1=Phillip G. | last2=Rawlins | first2=Gregory J. E. | last3=Shannon | first3=Gregory E. | title=Efficient Matrix Chain Ordering in Polylog Time | publisher=[[Society for Industrial and Applied Mathematics]] | location=Philadelphia | year=1998 | journal=SIAM Journal on Computing | issn=1095-7111 | volume=27 | issue=2 | pages=466–490 | doi=10.1137/S0097539794270698}}</ref>
| |
| | |
| ==Sub-linear time==
| |
| An algorithm is said to run in '''sub-linear time''' (often spelled '''sublinear time''') if ''T''(''n'') = o(''n''). In particular this includes algorithms with the time complexities defined above, as well as others such as the O(''n''<sup>½</sup>) [[Grover's algorithm|Grover's search]] algorithm.
| |
| | |
| Typical algorithms that are exact and yet run in sub-linear time use [[parallel algorithm|parallel processing]] (as the NC<sub>1</sub> matrix determinant calculation does), [[quantum algorithm|non-classical processing]] (as Grover's search does), or alternatively have guaranteed assumptions on the input structure (as the logarithmic time [[binary search algorithm|binary search]] and many tree maintenance algorithms do). However, languages such as the set of all strings that have a 1-bit indexed by the first log(n) bits may depend on every bit of the input and yet be computable in sub-linear time.
| |
| | |
| The specific term ''sublinear time algorithm'' is usually reserved to algorithms that are unlike the above in that they are run over classical serial machine models and are not allowed prior assumptions on the input.<ref>{{Cite journal
| |
| | last1 = Kumar | first1 = Ravi
| |
| | last2 = Rubinfeld | first2 = Ronitt
| |
| | title = Sublinear time algorithms
| |
| | journal = SIGACT News
| |
| | volume = 34
| |
| | issue = 4
| |
| | pages = 57–67
| |
| | url = http://www.cs.princeton.edu/courses/archive/spr04/cos598B/bib/kumarR-survey.pdf
| |
| | year = 2003}}</ref> They are however allowed to be [[randomized algorithm|randomized]], and indeed must be randomized for all but the most trivial of tasks.
| |
| | |
| As such an algorithm must provide an answer without reading the entire input, its particulars heavily depend on the access allowed to the input. Usually for an input that is represented as a binary string ''b''<sub>1</sub>,...,''b<sub>k</sub>'' it is assumed that the algorithm can in time O(1) request and obtain the value of ''b<sub>i</sub>'' for any ''i''.
| |
| | |
| Sub-linear time algorithms are typically randomized, and provide only [[approximation algorithm|approximate]] solutions. In fact, the property of a binary string having only zeros (and no ones) can be easily proved not to be decidable by a (non-approximate) sub-linear time algorithm. Sub-linear time algorithms arise naturally in the investigation of [[property testing]].
| |
| | |
| ==Linear time==
| |
| An algorithm is said to take '''linear time''', or '''O(''n'')''' time, if its time complexity is O(''n''). Informally, this means that for large enough input sizes the running time increases linearly with the size of the input. For example, a procedure that adds up all elements of a list requires time proportional to the length of the list. This description is slightly inaccurate, since the running time can significantly deviate from a precise proportionality, especially for small values of ''n''.
| |
| | |
| Linear time is often viewed as a desirable attribute for an algorithm. Much research has been invested into creating algorithms exhibiting (nearly) linear time or better. This research includes both software and hardware methods. In the case of hardware, some algorithms which, mathematically speaking, can never achieve linear time with standard [[computation model]]s are able to run in linear time. There are several hardware technologies which exploit [[Parallel computing|parallelism]] to provide this. An example is [[content-addressable memory]]. This concept of linear time is used in string matching algorithms such as the [[Boyer–Moore string search algorithm|Boyer-Moore Algorithm]] and [[Ukkonen's Algorithm]].
| |
| | |
| ==Linearithmic time==
| |
| A '''linearithmic function''' ([[portmanteau]] of ''linear'' and ''logarithmic'') is a function of the form ''n'' · log ''n'' (i.e., a [[product (mathematics)|product]] of a [[linear]] and a [[logarithm]]ic term). An algorithm is said to run in '''linearithmic time''' if ''T''(''n'') = '''O(''n'' log ''n'')'''. Compared to other functions, a linearithmic function is ω(''n''), o(''n''<sup>1+ε</sup>) for every ε > 0, and Θ(''n'' · log ''n''). Thus, a linearithmic term grows faster than a linear term but slower than any polynomial in ''n'' with exponent strictly greater than 1.
| |
| | |
| In many cases, the ''n'' · log ''n'' running time is simply the result of performing a Θ(log ''n'') operation ''n'' times. For example, [[binary tree sort]] creates a [[binary tree]] by inserting each element of the n-sized array one by one. Since the insert operation on a [[self-balancing binary search tree]] takes O(log ''n'') time, the entire algorithm takes linearithmic time.
| |
| | |
| [[Comparison sort]]s require at least linearithmic number of comparisons in the worst case because log(''n''!) = Θ(''n'' log ''n''), by [[Stirling's approximation]]. They also frequently arise from the [[recurrence relation]] ''T''(''n'') = 2 ''T''(''n''/2) + O(''n'').
| |
| | |
| Some famous [[algorithm]]s that run in linearithmic time include:
| |
| *[[Quicksort]] in the average case
| |
| *[[Heapsort]], [[merge sort]], [[introsort]], binary tree sort, [[smoothsort]], [[patience sorting]], etc. in the worst case
| |
| *[[Fast Fourier transform]]s
| |
| *[[Monge array]] calculation
| |
| | |
| ==Quasilinear time==
| |
| A generalization of linearithmic time is '''quasilinear time'''. An algorithm is said to run in quasilinear time if ''T''(''n'') = '''O(''n'' log<sup>''k''</sup> ''n'')''' for any constant ''k''; linearithmic time is the case ''k'' = 1. Quasilinear time algorithms are also o(''n''<sup>1+ε</sup>) for every ε > 0, and thus run faster than any polynomial in ''n'' with exponent strictly greater than 1.
| |
| | |
| Algorithms which run in quasilinear time, in addition to the linearithmic algorithms listed above, include:
| |
| * [[In-place merge sort]], O(''n'' log<sup>''2''</sup> ''n'')
| |
| | |
| ==Sub-quadratic time==
| |
| An [[algorithm]] is said to be '''subquadratic time''' if ''T''(''n'') = o(''n''<sup>2</sup>).
| |
| | |
| For example, most naïve comparison-based [[sorting algorithm]]s are quadratic (e.g. [[insertion sort]]), but more advanced algorithms can be found that are subquadratic (e.g. [[Shell sort]]). No general-purpose sorts run in linear time, but the change from quadratic to sub-quadratic is of great practical importance.
| |
| | |
| ==Polynomial time==
| |
| An algorithm is said to be of '''polynomial time''' if its running time is [[upper bound]]ed by a [[polynomial expression]] in the size of the input for the algorithm, i.e., ''T''(''n'') = O(''n''<sup>''k''</sup>) for some constant ''k''.<ref name=Sipser>{{Cite book| last=Sipser | first=Michael | authorlink=Michael Sipser | coauthors= | title=Introduction to the Theory of Computation | year=2006 | publisher=Course Technology Inc | location= | isbn=0-619-21764-2 | pages=}}</ref><ref>{{Cite book| last=Papadimitriou | first=Christos H. | authorlink=Christos H. Papadimitriou | coauthors= | title=Computational complexity | year=1994 | publisher=Addison-Wesley | location=Reading, Mass. | isbn=0-201-53082-1 | pages=}}</ref> [[Decision problem|Problems]] for which a polynomial time algorithm exists belong to the [[complexity class]] '''[[P (complexity)|P]]''', which is central in the field of [[computational complexity theory]]. [[Cobham's thesis]] states that polynomial time is a synonym for "tractable", "feasible", "efficient", or "fast".<ref>{{Cite book| last=Cobham | first=Alan | authorlink=Alan Cobham | year = 1965 | chapter = The intrinsic computational difficulty of functions | title = Proc. Logic, Methodology, and Philosophy of Science II | publisher = North Holland}}</ref>
| |
| | |
| Some examples of polynomial time algorithms:
| |
| * The [[quicksort]] sorting algorithm on ''n'' integers performs at most <math>An^2</math> operations for some constant ''A''. Thus it runs in time <math>O(n^2)</math> and is a polynomial time algorithm.
| |
| * All the basic arithmetic operations (addition, subtraction, multiplication, division, and comparison) can be done in polynomial time.
| |
| * [[Maximum matching]]s in [[Graph (mathematics)|graphs]] can be found in polynomial time.
| |
| | |
| ===Strongly and weakly polynomial time===
| |
| | |
| In some contexts, especially in [[Optimization (mathematics)|optimization]], one differentiates between '''strongly polynomial time''' and '''weakly polynomial time''' algorithms. These two concepts are only relevant if the inputs to the algorithms consist of integers.
| |
| | |
| Strongly polynomial time is defined in the arithmetic model of computation. In this model of computation the basic arithmetic operations (addition, subtraction, multiplication, division, and comparison) take a unit time step to perform, regardless of the sizes of the operands. The algorithm runs in strongly polynomial time if <ref>{{Cite book| last=Grötschel | first=Martin | coauthors = [[László Lovász]], [[Alexander Schrijver]] | year = 1988 | chapter = Complexity, Oracles, and Numerical Computation| title = Geometric Algorithms and Combinatorial Optimization | publisher = Springer | isbn=0-387-13624-X}}</ref>
| |
| | |
| # the number of operations in the arithmetic model of computation is bounded by a polynomial in the number of integers in the input instance; and
| |
| # the space used by the algorithm is bounded by a polynomial in the size of the input.
| |
| | |
| Any algorithm with these two properties can be converted to a polynomial time algorithm by replacing the arithmetic operations by suitable algorithms for performing the arithmetic operations on a [[Turing machine]]. If the second of the above requirement is not met, then this is not true anymore. Given the integer <math>2^n</math> (which takes up space proportional to n), it is possible to compute <math>2^{2^n}</math>
| |
| with n multiplications using [[repeated squaring]]. However, the space used to represent <math>2^{2^n}</math> is proportional to <math>2^n</math>, and thus exponential rather than polynomial in the space used to represent the input. Hence, it is not possible to carry out this computation in polynomial time on a Turing machine, but it is possible to compute it by polynomially many arithmetic operations.
| |
| | |
| Conversely, there are algorithms which run in a number of Turing machine steps bounded by a polynomial in the length of binary-encoded input, but do not take a number of arithmetic operations bounded by a polynomial in the number of input numbers. The [[Euclidean algorithm]] for computing the [[greatest common divisor]] of two integers is one example. Given two integers <math>a</math> and <math>b</math> the running time of the algorithm is bounded by <math>O((\log\ a + \log\ b)^2)</math> Turing machine steps. This is polynomial in the size of a binary representation of <math>a</math> and <math>b</math> as the size of such a representation is roughly <math>\log\ a + \log\ b</math>. At the same time, the number of arithmetic operations cannot be bound by the number of integers in the input (which is constant in this case, there are always only two integers in the input). Due to the latter observation, the algorithm does not run in strongly polynomial time. Its real running time depends on the magnitudes of <math>a</math> and <math>b</math> and not only on the number of integers in the input.
| |
| | |
| An algorithm which runs in polynomial time but which is not strongly polynomial is said to run in '''weakly polynomial time'''.<ref>{{Cite book| last=Schrijver | first=Alexander | authorlink = Alexander Schrijver| year = 2003 | chapter = Preliminaries on algorithms and Complexity | title = Combinatorial Optimization: Polyhedra and Efficiency | volume = 1 | publisher = Springer | isbn=3-540-44389-4}}</ref>
| |
| A well-known example of a problem for which a weakly polynomial-time algorithm is known, but is not known to admit a strongly polynomial-time algorithm,
| |
| is [[linear programming]]. Weakly polynomial-time should not be confused with [[pseudo-polynomial time]].
| |
| | |
| ===Complexity classes===
| |
| | |
| The concept of polynomial time leads to several complexity classes in computational complexity theory. Some important classes defined using polynomial time are the following.
| |
| | |
| * '''[[P (complexity)|P]]''': The [[complexity class]] of [[decision problem]]s that can be solved on a [[deterministic Turing machine]] in polynomial time.
| |
| * '''[[NP (complexity)|NP]]''': The complexity class of decision problems that can be solved on a [[non-deterministic Turing machine]] in polynomial time.
| |
| * '''[[ZPP (complexity)|ZPP]]''': The complexity class of decision problems that can be solved with zero error on a [[probabilistic Turing machine]] in polynomial time.
| |
| * '''[[RP (complexity)|RP]]''': The complexity class of decision problems that can be solved with 1-sided error on a probabilistic Turing machine in polynomial time.
| |
| * '''[[BPP (complexity)|BPP]]''': The complexity class of decision problems that can be solved with 2-sided error on a probabilistic Turing machine in polynomial time.
| |
| * '''[[BQP]]''': The complexity class of decision problems that can be solved with 2-sided error on a [[quantum Turing machine]] in polynomial time.
| |
| | |
| P is the smallest time-complexity class on a deterministic machine which is [[Robustness (computer science)|robust]] in terms of machine model changes. (For example, a change from a single-tape Turing machine to a multi-tape machine can lead to a quadratic speedup, but any algorithm that runs in polynomial time under one model also does so on the other.) Any given [[abstract machine]] will have a complexity class corresponding to the problems which can be solved in polynomial time on that machine.
| |
| | |
| ==Superpolynomial time==
| |
| An algorithm is said to take '''superpolynomial time''' if ''T''(''n'') is not bounded above by any polynomial. It is ω(''n''<sup>''c''</sup>) time for all constants ''c'', where ''n'' is the input parameter, typically the number of bits in the input.
| |
| | |
| For example, an algorithm that runs for 2<sup>''n''</sup> steps on an input of size ''n'' requires superpolynomial time (more specifically, exponential time).
| |
| | |
| An algorithm that uses exponential resources is clearly superpolynomial, but some algorithms are only very weakly superpolynomial. For example, the [[Adleman–Pomerance–Rumely primality test]] runs for ''n''<sup>O(log log ''n'')</sup> time on ''n''-bit inputs; this grows faster than any polynomial for large enough ''n'', but the input size must become impractically large before it cannot be dominated by a polynomial with small degree.
| |
| | |
| An algorithm that requires superpolynomial time lies outside the [[complexity class]] '''[[P (complexity)|P]]'''. [[Cobham's thesis]] posits that these algorithms are impractical, and in many cases they are. Since the [[P versus NP problem]] is unresolved, no algorithm for an [[NP-complete]] problem is currently known to run in polynomial time.
| |
| | |
| ==Quasi-polynomial time==
| |
| '''Quasi-polynomial time''' algorithms are algorithms which run slower than polynomial time, yet not so slow as to be exponential time. The worst case running time of a quasi-polynomial time algorithm is <math>2^{O((\log n)^c)}</math> for some fixed ''c''. The best-known classical algorithm for integer factorization, the [[general number field sieve]], which runs in time about <math>2^{\tilde{O}(n^{1/3})}</math> is ''not'' quasi-polynomial since the running time cannot be expressed as <math>2^{O((\log n)^c)}</math> for some fixed ''c''. If the constant "c" in the definition of quasi-polynomial time algorithms is equal to 1, we get a polynomial time algorithm, and if it is less than 1, we get a sub-linear time algorithm.
| |
| | |
| Quasi-polynomial time algorithms typically arise in reductions from an [[NP-hard]] problem to another problem. For example, one can take an instance of an NP hard problem, say [[3SAT]], and convert it to an instance of another problem B, but the size of the instance becomes <math>2^{O((\log n)^c)}</math>. In that case, this reduction does not prove that problem B is NP-hard; this reduction only shows that there is no polynomial time algorithm for B unless there is a quasi-polynomial time algorithm for 3SAT (and thus all of [[NP (complexity)|NP]]). Similarly, there are some problems for which we know quasi-polynomial time algorithms, but no polynomial time algorithm is known. Such problems arise in approximation algorithms; a famous example is the directed [[Steiner tree problem]], for which there is a quasi-polynomial time approximation algorithm achieving an approximation factor of <math>O(\log^3 n)</math> (n being the number of vertices), but showing the existence of such a polynomial time algorithm is an open problem.
| |
| | |
| The complexity class '''QP''' consists of all problems which have quasi-polynomial time algorithms. It can be defined in terms of [[DTIME]] as follows.<ref>{{ComplexityZoo|Class QP: Quasipolynomial-Time|Q#qp}}</ref>
| |
| :<math>\mbox{QP} = \bigcup_{c \in \mathbb{N}} \mbox{DTIME}(2^{(\log n)^c})</math>
| |
| | |
| ===Relation to NP-complete problems===
| |
| | |
| In complexity theory, the unsolved [[P versus NP]] problem asks if all problems in NP have polynomial-time algorithms. All the best-known algorithms for [[NP-complete]] problems like 3SAT etc. take exponential time. Indeed, it is conjectured for many natural NP-complete problems that they do not have sub-exponential time algorithms. Here "sub-exponential time" is taken to mean the second definition presented above. (On the other hand, many graph problems represented in the natural way by adjacency matrices are solvable in subexponential time simply because the size of the input is square of the number of vertices.) This conjecture (for the k-SAT problem) is known as the [[exponential time hypothesis]].<ref name="ETH">{{Cite journal| last1=Impagliazzo | first1=R. | last2=Paturi | first2=R. | title=On the complexity of k-SAT | publisher=[[Elsevier]] | year=2001 | journal=Journal of Computer and System Sciences | issn=1090-2724 | volume=62 | issue=2 | pages=367–375 | doi=10.1006/jcss.2000.1727}}</ref> Since it is conjectured that NP-complete problems do not have quasi-polynomial time algorithms, some inapproximability results in the field of [[approximation algorithms]] make the assumption that NP-complete problems do not have quasi-polynomial time algorithms. For example, see the known inapproximability results for the [[set cover]] problem.
| |
| | |
| ==Sub-exponential time==
| |
| The term '''sub-exponential time''' is used to express that the running time of some algorithm may grow faster than any polynomial but is still significantly smaller than an exponential. In this sense, problems that have sub-exponential time algorithms are somewhat more tractable than those that only have exponential algorithms. The precise definition of "sub-exponential" is not generally agreed upon,<ref>{{Cite web|url=http://scottaaronson.com/blog/?p=394 |title=A not-quite-exponential dilemma |author=Aaronson, Scott |date=5 April 2009 |work=Shtetl-Optimized |accessdate=2 December 2009}}</ref> and we list the two most widely used ones below.
| |
| | |
| ===First definition===<!-- [[SUBEXP]] redirects here -->
| |
| | |
| A problem is said to be sub-exponential time solvable if it can be solved in running times whose logarithms grow smaller than any given polynomial. More precisely, a problem is in sub-exponential time if for every ε > 0 there exists an algorithm which solves the problem in time O(2<sup>n<sup>ε</sup></sup>). The set of all such problems is the complexity class '''SUBEXP''' which can be defined in terms of [[DTIME]] as follows.<ref name="bpp">{{Cite journal| last1=Babai | first1=László | author1-link = László Babai | last2=Fortnow | first2=Lance | author2-link = Lance Fortnow | last3=Nisan | first3=N. | author3-link = Noam Nisan | last4=Wigderson | first4=Avi | author4-link = Avi Wigderson | title=BPP has subexponential time simulations unless EXPTIME has publishable proofs | publisher=[[Springer-Verlag]] | location=Berlin, New York | year=1993 | journal=Computational Complexity | volume=3 | issue=4 | pages=307–318 | doi=10.1007/BF01275486}}</ref><ref>{{ComplexityZoo|Class SUBEXP: Deterministic Subexponential-Time|S#subexp}}</ref><ref>{{Cite journal| last1=Moser | first1=P. | title=Baire's Categories on Small Complexity Classes | publisher=Springer-Verlag | location=Berlin, New York | year=2003 | journal=[[Lecture Notes in Computer Science]] | issn=0302-9743 | pages=333–342}}
| |
| </ref><ref>{{Cite journal| last1=Miltersen | first1=P.B. | title=DERANDOMIZING COMPLEXITY CLASSES | publisher=Kluwer Academic Pub | year=2001 | journal=Handbook of Randomized Computing | page=843}}</ref>
| |
| | |
| :<math>\text{SUBEXP}=\bigcap_{\varepsilon>0} \text{DTIME}\left(2^{n^\varepsilon}\right)</math>
| |
| | |
| Note that this notion of sub-exponential is non-uniform in terms of ε in the sense that ε is not part of the input and each ε may have its own algorithm for the problem.
| |
| | |
| ===Second definition===
| |
| Some authors define sub-exponential time as running times in 2<sup>o(''n'')</sup>.<ref name="ETH" /><ref>{{Cite journal| last1=Kuperberg | first1=Greg | title=A Subexponential-Time Quantum Algorithm for the Dihedral Hidden Subgroup Problem | publisher=[[Society for Industrial and Applied Mathematics]] | location=Philadelphia | year=2005 | journal=SIAM Journal on Computing | issn=1095-7111 | volume=35 | issue=1 | page=188}}</ref><ref>{{cite arxiv|eprint=quant-ph/0406151v1|author1=Oded Regev|title=A Subexponential Time Algorithm for the Dihedral Hidden Subgroup Problem with Polynomial Space|class=quant-ph|year=2004}}</ref> This definition allows larger running times than the first definition of sub-exponential time. An example of such a sub-exponential time algorithm is the best-known classical algorithm for integer factorization, the [[general number field sieve]], which runs in time about <math>2^{\tilde{O}(n^{1/3})}</math>, where the length of the input is ''n''. Another example is the best-known algorithm for the [[graph isomorphism problem]], which runs in time 2<sup>O(√(''n'' log ''n''))</sup>.
| |
| | |
| Note that it makes a difference whether the algorithm is allowed to be sub-exponential in the size of the instance, the number of vertices, or the number of edges. In [[parameterized complexity]], this difference is made explicit by considering pairs <math>(L,k)</math> of [[decision problem]]s and parameters ''k''. '''SUBEPT''' is the class of all parameterized problems that run in time sub-exponential in ''k'' and polynomial in the input size ''n'':<ref>{{Cite book
| |
| | last=Flum | first=Jörg
| |
| | last2=Grohe | first2=Martin
| |
| | title = Parameterized Complexity Theory | year = 2006 | publisher = Springer
| |
| | url = http://www.springer.com/east/home/generic/search/results?SGWID=5-40109-22-141358322-0
| |
| | isbn = 978-3-540-29952-3 |ref=harv |accessdate=2010-03-05| page=417}}</ref>
| |
| | |
| :<math>\text{SUBEPT}=\text{DTIME}\left(2^{o(k)} \cdot \text{poly}(n)\right).</math>
| |
| | |
| More precisely, SUBEPT is the class of all parameterized problems <math>(L,k)</math> for which there is a [[computable function]] <math>f : \mathbb N\to\mathbb N</math> with <math>f \in o(k)</math> and an algorithm that decides ''L'' in time <math>2^{f(k)} \cdot \text{poly}(n)</math>.
| |
| | |
| ====Exponential time hypothesis====
| |
| {{Main|Exponential time hypothesis}}
| |
| | |
| The '''exponential time hypothesis''' ('''ETH''') is that [[3SAT]], the satisfiability problem of Boolean formulas in [[conjunctive normal form]] with at most three literals per clause and with ''n'' variables, cannot be solved in time 2<sup>''o''(''n'')</sup>. More precisely, the hypothesis is that there is some absolute constant ''c''>0 such that 3SAT cannot be decided in time 2<sup>''cn''</sup> by any deterministic Turing machine. With ''m'' denoting the number of clauses, ETH is equivalent to the hypothesis that ''k''SAT cannot be solved in time 2<sup>''o''(''m'')</sup> for any integer ''k'' ≥ 3.<ref>{{Cite journal|first1=R.|last1=Impagliazzo|author1-link=Russell Impagliazzo|first2=R.|last2=Paturi|first3=F.|last3=Zane|title=Which problems have strongly exponential complexity?|journal=[[Journal of Computer and System Sciences]]|volume=63|issue=4|year=2001|pages=512–530|doi=10.1006/jcss.2001.1774}}</ref> The exponential time hypothesis implies [[P ≠ NP]].
| |
| | |
| ==Exponential time==
| |
| An algorithm is said to be '''exponential time''', if ''T''(''n'') is upper bounded by 2<sup>poly(''n'')</sup>, where poly(''n'') is some polynomial in ''n''. More formally, an algorithm is exponential time if ''T''(''n'') is bounded by O(2<sup>''n''<sup>''k''</sup></sup>) for some constant ''k''. Problems which admit exponential time algorithms on a deterministic Turing machine form the complexity class known as '''[[EXP]]'''.
| |
| :<math>\text{EXP} = \bigcup_{c \in \mathbb{N}} \text{DTIME}\left(2^{n^c}\right)</math>
| |
| | |
| Sometimes, exponential time is used to refer to algorithms that have ''T''(''n'') = 2<sup>O(''n'')</sup>, where the exponent is at most a linear function of ''n''. This gives rise to the complexity class '''[[E (complexity)|E]]'''.
| |
| :<math>\text{E} = \bigcup_{c \in \mathbb{N}} \text{DTIME}\left(2^{cn}\right)</math>
| |
| | |
| ==Double exponential time==
| |
| An algorithm is said to be [[double exponential function|double exponential]] time if ''T''(''n'') is upper bounded by 2<sup>2<sup>poly(''n'')</sup></sup>, where poly(''n'') is some polynomial in ''n''. Such algorithms belong to the complexity class [[2-EXPTIME]].
| |
| :<math>\mbox{2-EXPTIME} = \bigcup_{c \in \mathbb{N}} \mbox{DTIME}(2^{2^{n^c}})</math>
| |
| | |
| Well-known double exponential time algorithms include:
| |
| * Decision procedures for [[Presburger arithmetic]]
| |
| * Computing a [[Gröbner basis]] (in the worst case)
| |
| * [[Quantifier elimination]] on [[real closed field]]s takes at least doubly exponential time (but is not even known to be computable in [[ELEMENTARY]])
| |
| | |
| ==See also==
| |
| * [[L-notation]]
| |
| | |
| ==References==
| |
| {{Reflist|colwidth=33em}}
| |
| {{Use dmy dates|date=September 2010}}
| |
| | |
| {{DEFAULTSORT:Time Complexity}}
| |
| [[Category:Analysis of algorithms]]
| |
| [[Category:Computational complexity theory]]
| |
| [[Category:Computational resources]]
| |