算法基础-时间复杂度

计算机原理
  目录
  1. 1. 大O符号表示法
  2. 2. 常见时间复杂度量级
    1. 2.1. O(1)
    2. 2.2. O(n)
    3. 2.3. O(logN)
    4. 2.4. O(nlogN)
    5. 2.5. O(n^2)
    6. 2.6. O(n^3) O(n^k)
    7. 2.7. O(2^n)
  3. 3. 复杂度分析的4个高阶概念
    1. 3.1. 概念
    2. 3.2. 为什么要引入这4个概念？
    3. 3.3. 如何分析平均、均摊时间复杂度？
  4. 4. 总结

算法基础之时间复杂度

对于算法的衡量一般是从两个维度进行的，一是空间维度，即算法执行所需要占据的内存空间；一是时间维度，即算法执行所需要的时间，今天主讲时间维度。

大O符号表示法

对于时间复杂度的衡量，我们最常见的就是使用大O符号表示法，例如O(1),O(n)等。之所以采用这样的方式衡量，是因为在不同配置的计算机上，相同的算法代码所呈现出来的性能也不尽相同。所以引入大O符号表示法可以使算法执行所消耗的时间标准化，更加易于对比。
大O符号表示法的完整格式是T(n)=O(f(n))，这个函数表示的是代码执行次数与所使用时间之间的正比例关系。其中f(n)表示算法中每行代码执行次数的和，O()表示一个正比例关系。所以大O符号表示法所表示的是算法执行时间的增长变化趋势的，而不是算法实际的执行时间。在使用大O符号表示法的时候，我们一般会假设算法中每一行代码的执行时间都是一样，也就是一个单位时间会运行一行代码，这样我们就能够方便的计算f(n)了。

常见时间复杂度量级

一般在代码设计中长长的出现的时间复杂度量级主要有以下这些：

  • 常数阶O(1)。
  • 对数阶O(logN)。
  • 线性阶O(n) 。
  • 线性对数阶O(nlogN)。
  • 平方阶O(n^2)。
  • 立方阶O(n^3)。
  • K方阶O(n^k)。
  • 指数阶O(2^n)。
  • 组合阶O(n!)。

以上这些复杂度量级从上到下所表示的复杂度越来越大，执行效率也越来越低。下面就一些示例来说明不同形式的代码其时间复杂度的量级。

O(1)

代码中没有循环结构，无论执行多少行，代码所消耗的时间始终固定，不随着某个变量的操作发生变化，其复杂度就是O(1) 。

1
2
3
4
i = 1
j = 2
i += 1
j += 2

O(n)

代码中只有一层循环结构，没有任何嵌套的循环结构，代码执行所消耗的时间只与循环控制变量线性相关，那么这段代码的复杂度就是O(n) 。

1
2
3
4
int n =100;
for(int i=0; i<n; i++){
  System.out.println(i);
}

O(logN)

代码中同样只有一层循环结构，没有任何嵌套的循环结构，但是代码执行所消耗的时间与循环控制变量指数相关，那么这段代码的复杂度就是O(logN)。

1
2
3
4
5
6
7
8
9
int i = 1;
int n = 1024;
while(i < n){
    i = i*2;
}
// 或者
for(int i=0; i<n; i*=2){
    System.out.println(i);
}

从例子可以看出，时间复杂度是O(log2(n)),但是2可以忽略掉，直接写成O(log(n))。

O(nlogN)

线性对数阶量级中就已经开始出现多层的循环结构了，在复杂度为O(nlogN)量级的代码中，有两层循环结构，其中一层为O(n)量级的循环，一层为O(logN)量级的循环。

1
2
3
4
5
6
7
int n =100;
int m = 1024;
for(int i=0; i<n; i++){
  while(i < m){
    i = i*2;
  }
}

O(n^2)

平方阶O(n²) 就是把 O(n) 的代码再嵌套循环一遍，它的时间复杂度就是 O(n²) 了。

1
2
3
4
5
6
7
int n = 100;
int m = 100;
for (i=0; i < n ; i++){
  for(i=0; i < m ;i++){
    System.out.println(i);
  }
}

O(n^3) O(n^k)

立方阶则是3层循环嵌套。
K方阶则是k层循环嵌套。

O(2^n)

下例从出现递归的时候，T(0) = T(1) = 1，同时 T(n) = T(n - 1) + T(n - 2) + 1，这里的 1 是其中的加法算一次执行。显然 T(n) = T(n - 1) + T(n - 2) 是一个斐波那契数列，通过归纳证明法可以证明，当 n >= 1 时 T(n) < (5/3)^n，同时当 n > 4 时 T(n) >= (3/2)^n。所以该方法的时间复杂度可以表示为 O((5/3)^n)，简化后为 O(2^n)。

1
2
3
4
5
6
7
long function1(int n) {    
  if (n <= 1) {        
    return 1;
  } else {        
    return function1(n - 1) + function1(n - 2);
  }
}

复杂度分析的4个高阶概念

概念

  • 最好情况时间复杂度：代码在最理想情况下执行的时间复杂度。
  • 最坏情况时间复杂度：代码在最坏情况下执行的时间复杂度。
  • 平均时间复杂度：用代码在所有情况下执行的次数的加权平均值表示。
  • 均摊时间复杂度：在代码执行的所有复杂度情况中绝大部分是低级别的复杂度，个别情况是高级别复杂度且发生具有时序关系时，可以将个别高级别复杂度均摊到低级别复杂度上。基本上均摊结果就等于低级别复杂度。

为什么要引入这4个概念？

同一段代码在不同情况下时间复杂度会出现量级差异，为了更全面，更准确的描述代码的时间复杂度，所以引入这4个概念。代码复杂度在不同情况下出现量级差别时才需要区别这四种复杂度。大多数情况下，是不需要区别分析它们的。

如何分析平均、均摊时间复杂度？

平均时间复杂度：代码在不同情况下复杂度出现量级差别，则用代码所有可能情况下执行次数的加权平均值表示。
均摊时间复杂度：两个条件满足时使用：1）代码在绝大多数情况下是低级别复杂度，只有极少数情况是高级别复杂度；2）低级别和高级别复杂度出现具有时序规律。均摊结果一般都等于低级别复杂度。

总结

以上是浅浅的介绍下算法的时间复杂度内容。
最后介绍一个图形工具数学工具
进入网站后，点击函数图像绘制工具，可以把复杂度量级以图形的方式直观的展示出来。

  面试题   算法