# 时间复杂度

## 常见时间复杂度列表

（小于1次）幂时间 $O(n^c)$，其中 $0 < c < 1$ $n^{\frac{1}{2}}$$n^{\frac{2}{3}}$ K-d树的搜索操作

## 常数时间

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


## 对数时间

// 递归输出一个字符串的右半部分
var right = function(str)
{
var length = str.length;

// 辅助函数
var help = function(index)
{

// 递归情况：输出右半部分
if(index < length){

// 输出从 index 到数组末尾的部分
console.log(str.substring(index, length));

// 递归调用：调用辅助函数，将右半部分作为参数传入
help(Math.ceil((length + index)/2));
}

// 基本情况：什么也不做
}
help(0);
}


## 幂对数时间

An algorithm is said to run in polylogarithmic time if T(n) = O((log n)k), for some constant k. For example, matrix chain ordering can be solved in polylogarithmic time on a Parallel Random Access Machine.[3]

## 次线性时间

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½) Grover's search algorithm.

Typical algorithms that are exact and yet run in sub-linear time use parallel processing (as the NC1 matrix determinant calculation does), non-classical processing (as Grover's search does), or alternatively have guaranteed assumptions on the input structure (as the logarithmic time 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.[4] They are however allowed to be 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 b1,...,bk it is assumed that the algorithm can in time O(1) request and obtain the value of bi for any i.

Sub-linear time algorithms are typically randomized, and provide only 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 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 models are able to run in linear time. There are several hardware technologies which exploit 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 Algorithm and Ukkonen's Algorithm.

## 线性对数（准线性）时间

A linearithmic function (portmanteau of linear and logarithmic) is a function of the form n · log n (i.e., a product of a linear and a logarithmic 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(n1+ε) 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.

An algorithm is said to run in quasilinear time if T(n) = O(n logk n) for any constant k. Quasilinear time algorithms are also o(n1+ε) for every ε > 0, and thus run faster 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.

Some famous algorithms that run in linearithmic time include:

An algorithm is said to be subquadratic time if T(n) = o(n2).

For example, most naïve comparison-based sorting algorithms 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.

## 多项式时间

An algorithm is said to be of polynomial time if its running time is upper bounded by a polynomial expression in the size of the input for the algorithm, i.e., T(n) = O(nk) for some constant k.[5][6] Problems for which a polynomial time algorithm exists belong to the complexity class 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".[7]

Some examples of polynomial time algorithms:

• The quicksort sorting algorithm on n integers performs at most $An^2$ operations for some constant A. Thus it runs in time $O(n^2)$ and is a polynomial time algorithm.
• All the basic arithmetic operations (addition, subtraction, multiplication, division, and comparison) can be done in polynomial time.
• Maximum matchings in graphs can be found in polynomial time.

### 强多项式时间与弱多项式时间

In some contexts, especially in 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 [8]

1. 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
2. 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 $2^n$ (which takes up space proportional to n), it is possible to compute $2^{2^n}$ with n multiplications using repeated squaring. However, the space used to represent $2^{2^n}$ is proportional to $2^n$, 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 $a$ and $b$ the running time of the algorithm is bounded by $O((\log\ a + \log\ b)^2)$ Turing machine steps. This is polynomial in the size of a binary representation of $a$ and $b$ as the size of such a representation is roughly $\log\ a + \log\ b$. 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 is 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 $a$ and $b$ 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.[9] 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.

### 复杂度类

• P：包含可以使用确定型图灵机在多项式时间内解决的决定性问题
• NP：包含可以使用非确定型图灵机在多项式时间内解决的决定性问题。
• ZPP：包含可以使用概率图灵机在多项式时间内零错误解决的决定性问题。
• RP：包含可以使用概率图灵机在多项式时间内解决的决定性问题，但它给出的两种答案中（是或否）只有一种答案是一定正确的，另一种则有几率不正确。
• BPP：包含可以使用概率图灵机在多项式时间内解决的决定性问题，它给出的答案有错误的概率在某个小于 0.5 的常数之内。
• BQP：包含可以使用量子图灵机在多项式时间内解决的决定性问题，它给出的答案有错误的概率在某个小于 0.5 的常数之内。

## 超越多项式（superpolynomial）时间

An algorithm is said to take superpolynomial time if T(n) is not bounded above by any polynomial. It is ω(nc) 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 2n 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 nO(log log n) 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 has been proven to require superpolynomial time cannot be solved in polynomial time, and so is known to lie outside the complexity class P. Cobham's thesis conjectures that these algorithms are impractical, and in many cases they are. Since the P versus NP problem is unresolved, no algorithm for a NP-complete problem is currently known to run in 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 $2^{O((\log n)^c)}$ for some fixed c. The best-known classical algorithm for integer factorization, the general number field sieve, which runs in time about $2^{\tilde{O}(n^{1/3})}$ is not quasi-polynomial since the running time cannot be expressed as $2^{O((\log n)^c)}$ 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 $2^{O((\log n)^c)}$. 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). 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 $O(\log^3 n)$ (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.[10]

$\mbox{QP} = \bigcup_{c \in \mathbb{N}} \mbox{DTIME}(2^{(\log n)^c})$

### 与NP完全问题的关系

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.[11] 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,[12] and we list the two most widely used ones below.

### 第一定义

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(2nε). The set of all such problems is the complexity class SUBEXP which can be defined in terms of DTIME as follows.[2][13][14][15]

$\text{SUBEXP}=\bigcap_{\varepsilon>0} \text{DTIME}\left(2^{n^\varepsilon}\right)$

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.

### 第二定义

Some authors define sub-exponential time as running times in 2o(n).[11][16][17] 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 $2^{\tilde{O}(n^{1/3})}$, where the length of the input is n. Another example is the best-known algorithm for the graph isomorphism problem, which runs in time 2O(√(n log n)).

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 $(L,k)$ of decision problems 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:[18]

$\text{SUBEPT}=\text{DTIME}\left(2^{o(k)} \cdot \text{poly}(n)\right).$

More precisely, SUBEPT is the class of all parameterized problems $(L,k)$ for which there is a computable function $f : \mathbb N\to\mathbb N$ with $f \in o(k)$ and an algorithm that decides L in time $2^{f(k)} \cdot \text{poly}(n)$.

#### 指数时间假设

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 2o(n). More precisely, the hypothesis is that there is some absolute constant c>0 such that 3SAT cannot be decided in time 2cn by any deterministic Turing machine. With m denoting the number of clauses, ETH is equivalent to the hypothesis that kSAT cannot be solved in time 2o(m) for any integer k ≥ 3.[19] The exponential time hypothesis implies P ≠ NP.

## 指数时间

An algorithm is said to be exponential time, if T(n) is upper bounded by 2poly(n), where poly(n) is some polynomial in n. More formally, an algorithm is exponential time if T(n) is bounded by O(2nk) for some constant k. Problems which admit exponential time algorithms on a deterministic Turing machine form the complexity class known as EXP.

$\text{EXP} = \bigcup_{c \in \mathbb{N}} \text{DTIME}\left(2^{n^c}\right)$

Sometimes, exponential time is used to refer to algorithms that have T(n) = 2O(n), where the exponent is at most a linear function of n. This gives rise to the complexity class E.

$\text{E} = \bigcup_{c \in \mathbb{N}} \text{DTIME}\left(2^{cn}\right)$

## 双重指数时间

An algorithm is said to be 双重指数 time if T(n) is upper bounded by 22poly(n), where poly(n) is some polynomial in n. Such algorithms belong to the complexity class 2-EXPTIME.

$\mbox{2-EXPTIME} = \bigcup_{c \in \mathbb{N}} \mbox{DTIME}(2^{2^{n^c}})$

Well-known double exponential time algorithms include:

## 參考資料

1. ^ Mehlhorn, Kurt; Naher, Stefan. Bounded ordered dictionaries in O(log log N) time and O(n) space. Information Processing Letters. 1990, 35 (4): 183. doi:10.1016/0020-0190(90)90022-P.
2. ^ 2.0 2.1 Babai, László; Fortnow, Lance; Nisan, N.; Wigderson, Avi. BPP has subexponential time simulations unless EXPTIME has publishable proofs. Computational Complexity (Berlin, New York: Springer-Verlag). 1993, 3 (4): 307–318. doi:10.1007/BF01275486.
3. ^ Bradford, Phillip G.; Rawlins, Gregory J. E.; Shannon, Gregory E. Efficient Matrix Chain Ordering in Polylog Time. SIAM Journal on Computing (Philadelphia: Society for Industrial and Applied Mathematics). 1998, 27 (2): 466–490. doi:10.1137/S0097539794270698. ISSN 1095-7111.
4. ^ Kumar, Ravi; Rubinfeld, Ronitt. Sublinear time algorithms. SIGACT News. 2003, 34 (4): 57–67.
5. ^ Sipser, Michael. Introduction to the Theory of Computation. Course Technology Inc. 2006. ISBN 0-619-21764-2.