本文共 2103 字，大约阅读时间需要 7 分钟。

【转载】

时间复杂度

一个算法执行所耗费的时间，从理论上是不能算出来的，必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试，只需知道哪个算法花费的时间多，哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或「时间频度」。记为T(n)。

时间频度T(n)中，n称为问题的规模，当n不断变化时，时间频度T(n)也会不断变化。但有时我们想知道它变化时呈现什么规律，为此我们引入时间复杂度的概念。算法的时间复杂度也就是算法的时间度量，记作：T(n) = O(f(n))。它表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐进时间复杂度，简称「时间复杂度」。

这种表示方法我们称为「 大O符号表示法 」，又称为渐进符号，是用于描述函数渐进行为的数学符号

常见的时间复杂度量级有：

常数阶$O(1)$

线性阶$O(n)$ 平方阶$O(n^2)$ 立方阶$O(n^3)$ 对数阶$O(logn)$ 线性对数阶$O(nlogn)$ 指数阶$O(2^n)$ 常数阶$O(1)$ $O(1)$，表示该算法的执行时间（或执行时占用空间）总是为一个常量，不论输入的数据集是大是小，只要是没有循环等复杂结构，那这个代码的时间复杂度就都是O(1)，如：

int i = 1;int j = 2;int k = i + j;

上述代码在执行的时候，它消耗的时候并不随着某个变量的增长而增长，那么无论这类代码有多长，即使有几万几十万行，都可以用$O(1)$来表示它的时间复杂度。

线性阶$O(n)$

$O(n)$，表示一个算法的性能会随着输入数据的大小变化而线性变化，如

for (int i = 0; i < n; i++) {
   	 j = i;   j++;}

这段代码，for循环里面的代码会执行n遍，因此它消耗的时间是随着n的变化而变化的，因此这类代码都可以用$O(n)$来表示它的时间复杂度。

平方阶$O(n^2)$

$O(n²)$ 表示一个算法的性能将会随着输入数据的增长而呈现出二次增长。最常见的就是对输入数据进行嵌套循环。如果嵌套层级不断深入的话，算法的性能将会变为立方阶$O(n3)$，$O(n4)$，$O(n^k)$以此类推

for(x=1; i<=n; x++){
      for(i=1; i<=n; i++){
          j = i;       j++;    }}

指数阶$O(2^n)$

$O(2^n)$，表示一个算法的性能会随着输入数据的每次增加而增大两倍，典型的方法就是裴波那契数列的递归计算实现

int Fibonacci(int number){
       if (number <= 1) return number;    return Fibonacci(number - 2) + Fibonacci(number - 1);}

对数阶$O(logn)$

int i = 1;while(i

上面的代码，在while循环里面，每次都将 i 乘以 2，乘完之后，i 距离 n 就越来越近了，直到i不小于n退出。我们试着求解一下，假设循环次数为x，也就是说 2 的 x 次方等于 n，则由2^x=n得出x=log₂n。因此这个代码的时间复杂度为$O(logn)$

线性对数阶$O(nlogn)$

线性对数阶$O(nlogn) $，就是将时间复杂度为对数阶$O(logn)$的代码循环n遍的话，那么它的时间复杂度就是n\ast O(logN)，也就是了$O(nlogn)$，如下，

for(m=1; m

除此之外，其实还有平均情况复杂度、最好时间复杂度、最坏时间复杂度。。。一般没有特殊说明的情况下，都是值最坏时间复杂度。