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

一、时间 空间复杂度

• 时间复杂度的全称是渐进时间复杂度（asymptotic time complexity），表示算法的执行时间与数据规模之间的增长关系。
• 空间复杂度全称就是渐进空间复杂度（asymptotic space complexity），表示算法的存储空间与数据规模之间的增长关系。

1. Big O notation

大 O 时间复杂度实际上并不具体表示代码真正的执行时间，而是表示代码执行时间随数据规模增长的变化趋势，所以，也叫作渐进时间复杂度（asymptotic time complexity），简称时间复杂度。

T(n) 表示代码执行的时间；n 表示数据规模的大小；f(n) 表示每行代码执行的次数总和。因为这是一个公式，所以用 f(n) 来表示。公式中的 O，表示代码的执行时间 T(n) 与 f(n) 表达式成正比。

O(1) : Constant Complexity : Constant 常数复杂度

O(log n) : Logarithmic Complexity : 对数复杂度

O(n) : Linear Complexity : 线性时间复杂度

O(n²) : N square Complexity : 平方

O(n³) : N square Complexity : 立方

O(2ⁿ) : Exponential Growth : 指数

O(n!) : Factorial : 阶乘

注意 : 只看最高复杂度的运算

例子

• O(1) :

  int n = 1000;System.out.println("Hey - your input is:" + n);

• O(log n) :

  for(int i = 1; i <= n; i = i * 2){
       	System.out.println("Hey - I'm busy looking at:" + i);}

• O(n) :

  for(int i = 1; i <= n; i++){
       	System.out.println("Hey - I'm busy looking at:" + i);}

• O(n²) :

  for(int i = 1; i <= n; i++){
       	for(int j = 1; j <= n; j++){
       		System.out.println("Hey - I'm busy looking at:" + i + " and " + j);    }}

• O(n³) :

  for(int i = 1; i <= n; i++){
       	for(int j = 1; j <= n; j++){
       		for(int k = 1; j <= n; j++){
       			System.out.println("Hey - I'm busy looking at:" + i + " and " + j + " and " + k);        }    }}

• O(2ⁿ) :

  for(int i = 1; i <= Math.pow(2,n), i++){
       	System.out.println("Hey - I'm busy looking at:" + i);}

• O(n!) :

  for(int i = 1; i <= factorial(n); i++){
       	System.out.println("Hey - I'm busy looking at:" + i + " and " + j);}

2. 时间复杂度分析

1. 只关注循环执行次数最多的一段代码
2. 加法法则：总的时间复杂度就等于量级最大的那段代码的时间复杂度。
3. 乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

3. 常见递归算法时间复杂度

4. 几种常见时间复杂度实例分析

这些可以分为两类

• 多项式量级
• 非多项式量级

其中，非多项式量级只有两个：O(2ⁿ)和O(n!)。当数据规模 n 越来越大时，非多项式量级算法的执行时间会急剧增加，求解问题的执行时间会无限增长。

1. O(1)：一般情况下，只要算法中不存在循环语句、递归语句，即使有成千上万行的代码，其时间复杂度也是Ο(1)。
2. O(log n)、O(nlog n)：一般情况下，变量i的变化为i = i * k，则时间复杂度为log_kn。由于在采用大 O 标记复杂度的时候，可以忽略系数，即 O(Cf(n)) = O(f(n))。因此，忽略对数底数，统一表示为O(log n)。O(nlog n)即为外层循环n次。
3. O(m+n)、O(m*n)：一般情况下，m 和 n 是表示两个数据规模。无法事先评估 m 和 n 谁的量级大，所以在表示复杂度的时候，就不能简单地利用加法法则，省略掉其中一个。所以，代码的时间复杂度就是 O(m+n)。

总结：

• 单段代码看高频：比如循环。
• 多段代码取最大：比如一段代码中有单循环和多重循环，那么取多重循环的复杂度。
• 嵌套代码求乘积：比如递归、多重循环等
• 多个规模求加法：比如方法有两个参数控制两个循环的次数，那么这时就取二者复杂度相加。

5. 空间复杂度

常见的空间复杂度就是 O(1)、O(n)、O(n² )，像 O(log n)、O(nlog n)

6. 最好、最坏、平均、均摊时间复杂度

• 最好情况时间复杂度（best case time complexity）：在最理想的情况下，执行这段代码的时间复杂度。

• 最坏情况时间复杂度（worst case time complexity）：在最糟糕的情况下，执行这段代码的时间复杂度。

• 平均情况时间复杂度（average case time complexity）：用代码在所有情况下执行的次数的加权平均值表示。

  以如下代码为例：查找x在数组中的下标

  // n表示数组array的长度int find(int[] array, int n, int x) {
         int i = 0;  int pos = -1;  for (; i < n; ++i) {
           if (array[i] == x) {
              pos = i;       break;    }  }  return pos;}

  平均情况时间复杂度为：（每一种情况需要遍历的元素个数 × 每一种情况出现的可能性）求和。即为下图：

  

  这个值就是概率论中的加权平均值，也叫作期望值，所以平均时间复杂度的全称应该叫加权平均时间复杂度或者期望时间复杂度。

• 均摊时间复杂度（amortized time complexity）：在代码执行的所有复杂度情况中绝大部分是低级别的复杂度，个别情况是高级别复杂度且发生具有时序关系时，可以将个别高级别复杂度均摊到低级别复杂度上。基本上均摊结果就等于低级别复杂度。

  均摊时间复杂度对应的分析方法：摊还分析（或者叫平摊分析）

  以如下代码为例：

  // array表示一个长度为n的数组// 代码中的array.length就等于nint[] array = new int[n];int count = 0;void insert(int val) {
          if (count == array.length) {
             int sum = 0;      for (int i = 0; i < array.length; ++i) {
                sum = sum + array[i];      }      array[0] = sum;      count = 1;   }   array[count] = val;   ++count;}

  向数组中插入数据，如果数组已满，遍历数组求和，并将结果存储在数组第一个位置，随后进行后续插入操作

  每种情况发生的概率一样，但有些情况所需要执行的操作数据次数与其他情况不同，可能导致如下加权平均计算：

  

  大体思路：每一次 O(n) 的插入操作，都会跟着 n-1 次 O(1) 的插入操作，所以把耗时多的那次操作均摊到接下来的 n-1 次耗时少的操作上，均摊下来，这一组连续的操作的均摊时间复杂度就是 O(1)。

• 均摊时间复杂度应用场景

  对一个数据结构进行一组连续操作中，大部分情况下时间复杂度都很低，只有个别情况下时间复杂度比较高，而且这些操作之间存在前后连贯的时序关系，这个时候，我们就可以将这一组操作放在一块儿分析，看是否能将较高时间复杂度那次操作的耗时，平摊到其他那些时间复杂度比较低的操作上。而且，在能够应用均摊时间复杂度分析的场合，一般均摊时间复杂度就等于最好情况时间复杂度。

转载地址：https://kaisarh.blog.csdn.net/article/details/117339223 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！