搞编程，你必知必会的复杂度分析

在开发中，我们会经常听到关于时间复杂度、空间复杂度相关词汇，如果你没有这方面的知识，你肯定会一脸懵逼。那什么是时间复杂度、空间复杂度还有我们又怎么去分析？首先我们先来弄清楚我们为什么需要做复杂度分析。

为什么需要复杂度分析？

真实的时间复杂度、空间复杂度我们需要在机器上执行我们编写的代码，才能统计出我们的代码这这个环境下的真实时间复杂度、空间复杂度。这种方法统计出来的结果非常准确，但是极限性也非常大。

1. 测试结果非常依赖测试环境

测试环境中硬件的不同会对测试结果有很大的影响。比如，拿同样一段代码，分别用 Intel Core i9 处理器和 IntelCore i3处理器来运行，不用说，i9处理器要比 i3 处理器执行的速度快很多。还有，比如原本在这台机器上 a 代码执行的速度比 b 代码要快，当换到另一台机器上时，可能 会有截然相反的结果。

2. 测试结果受数据规模的影响很大

比如排序算法，对同一个排序算法，待排序数据的有序度不一样，排序的执行时间就会有很大的差别。极端情况下，如果数据已经是有序的，那排序算法不需要做任何操作，执行时间就会非常短。除此之外，如果测试数据规模太小，测试结果可能无法真实地反应算法的性能。比如，对于小规模的数据排序，插入排序可能反倒会比快速排序要快！

那能不能不用具体的测试数据来测试，就可以粗略地估计算法的执行效率的方法？答案是肯定的，也就是我们的主题时间复杂度、空间复杂度的分析，一般用大O公式来进行代码时间复杂度、空间复杂度的预测分析。

大 O 复杂度表示法

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

假设每行代码的执行时间为time，我们来粗略估计一下这段代码块的执行总时间，第二行代码执行需要1个time，第3、4行代码都执行了n遍，所以需要的时间为n _time，第6行代码执行的时间为1个time，所以整个代码块的执行时间为(2n+2)_ time，如果我们用 T(n) 函数来表示代码的执行总时间，那么T(n) = (2n+2) * time可以看出 T(n) 与 n 成正比关系。这就可以用大O公式来表示。

大O公式：T(n)=O(f(n))

T(n) 表示代码执行的时间；n 表示数据规 模的大小；f(n) 表示每行代码执行的次数总和。 O 表示代码的执行时间 T(n) 与 f(n) 表达式成正比。这就是大 O 时间复杂度表示法。大 O时间复杂度实际上并不具体表示代码真正的执行时间，而是表示代码执行时间随 数据规模增长的变化趋势，所以，也叫作渐进时间复杂度（asymptotic time complexity），简称时间复杂度。 当 n 很大时，你可以把它想象成 10000、100000。而公式中的低阶、常量、系数三部分并不左右增 长趋势，所以都可以忽略。我们只需要记录一个最大量级就可以了，所以我们示例中的总时间就可以用 T(n) =O(n) 来标识。

时间复杂度分析

前面我们已经了解了大O公式，那我们如何进行代码的复杂度分析呢？可以从以下三个准则入手。

1、只关注循环执行次数最多的一段代码

我们知道用大O公式来表示时间复杂度的时候，忽略了常量、低阶、系数等，我们只需要关注循环执行次数最多的那一段代码就可以了，这段代码执行的次数 n 就是整个代码块的时间复杂度。为了方便我们理解这段话，我们用上面的代码来分析一下，加强理解。

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

代码 2、6 都是常量级的执行时间，对时间复杂度没有影响，执行最多的代码是 3、4 两行代码，一共执行了 n 次，所以整个代码块的时间复杂度为 O(n)

2、总复杂度等于量级最大的那段代码的复杂度

1    public void test(int n) {
2        for (int i = 0; i < n; i++) {
3            System.out.println(i);
4        }
5        for (int i = 0; i < n; i++) {
6            for (int j = 0; j < n; j++) {
7                System.out.println(i * j);
8            }
9        }
10    }

这段代码有两个时间复杂度，2-4 行代码的时间复杂度 T1(n) = O(n)，5-8 行代码的时间复杂度为 T2(n) = O(n²)。当 n 无限大的时候，T1(n) 对整个代码块的时间复杂度的影响是可以忽略的，整个代码块的时间复杂度就为 T2(n)=O(n²)，换句话说总的时间复杂度就等于量级最大的那段代码的时间复杂度。那我们将这个规律抽象成公式就是： 如果 T1(n)=O(f(n))，T2(n)=O(g(n))；那么 T(n)=T1(n)+T2(n)=max(O(f(n)),O(g(n)))=O(max(f(n),g(n)))

3、嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

1    public void test(int n) {
2        for (int i = 0; i < n; i++) {
3            for (int j = 0; j < n; j++) {
4                System.out.println(i * j);
5            }
6       }
7    }

这段代码中第二行代码的复杂度为T1(n)=O(n)，第3行代码块的T2(n)=O(n)，第四行代码的复杂度为O(1)可以忽略，因为这段代码是循环，所以时间复杂度T(n) = T1(n) T2(n) = O(n n) = O(n²)

通过上面的三种准则就能够很好的分析代码的时间复杂度，虽然代码千奇百怪，但是常见的复杂度量级并不多，我们来看看几种常见时间复杂度。

• 常数阶O(1)
• 对数阶O(logN)
• 线性阶O(n)
• 线性对数阶O(nlogN)
• 平方阶O(n²)
• 立方阶O(n³)
• K次方阶O(n^k)
• 指数阶(2^n)

上面从上至下依次的时间复杂度越来越大，执行的效率越来越低，我们来看看几种常见复杂的案例。

常数阶O(1)

常数阶非常简单，就是没有变量，都是常量，那样代码的时间复杂度就为 O(1)。下面两段代码的时间复杂度都为 O(1)。

public void test(){
    for (int i = 0;i <100;i++){
        System.out.println(i);
    }
}

public void sum(int n) {
    int i = 2;
    int j = 6;
    int sum = i + j;
    System.out.println(sum);
}

对数阶O(logN)

 i=1; 
 while (i <= n) { 
     i = i * 2;
 }

从上面代码可以看到，在while循环里面，每次都将 i 乘以 2，乘完之后，i 距离 n 就越来越近了。我们试着求解一下，假设循环x次之后，i 就大于 2 了，此时这个循环就退出了，也就是说 2 的 x 次方等于 n，那么 x = log2^n

也就是说当循环 log2^n 次以后，这个代码就结束了。因此这个代码的时间复杂度为：O(logn)

线性阶O(n)

public void sum(int n) {
    int sum = 0;
    for (int i = 1; i <= n; i++) {
        sum += i;
    }
    System.out.println(sum);
}

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

线性对数阶O(nlogN)

public void test1(int n) {
    for (int i = 0; i < n; i++) {
        int m = 0;
        while (m < n) {
            m *= 2;
        }
    }
}

线性对数阶O(nlogN) 其实非常容易理解，将时间复杂度为O(logn)的代码循环N遍的话，那么它的时间复杂度就是 n * O(logN)，也就是了 O(nlogN)。

平方阶O(n²)

public void test(int n) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            System.out.println(i * j);
        }
    }
}

平方阶 O(n²) 就是两层循环，每层循环的次数是一个变量，这种的两层循环的代码的时间复杂度都可以用 O(n²) 表示。立方阶O(n³)、K次方阶O(n^k)跟这个一样，只是多层循环而已。

上面就是常用时间复杂度的案例，在时间复杂度分析中，你也许还听说过最好情况时间复杂度、最坏情况时间复杂度、平均情况时间复杂，那这些又是什么呢？先来看一段案例。

public 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;
}

上面的代码是在数组中找出值等于x的下标。根据上面学习的大O公式，这段代码的时间复杂度为 O(n)，但是这段代码的时间复杂度一定为O(n)吗？不一定的，如果数组中第一个元素正好是要查找的变量x，那就不需要继续遍历剩下的 n-1 个数据了，那时间复杂度就是O(1)。但如果数组中不存在变量x，那就需要把整个数组都遍历一遍，时间复杂度就成了O(n)。所以，不同的情况下，这段代码的时间复杂度是不一样的。

为了表示代码在不同情况下的不同时间复杂度，就需要引入上面提到的三个概念：最好情况时间复杂度、最坏情况时间复杂度和平均情况时间复杂度。

最好情况时间复杂度就是，在最理想的情况下，执行这段代码的时间复杂度。就像上面的示例，在最理想的情况下，要查找的变量x正好是数组的第一个元素，这个时候对应的时间复杂度就是最好情况时间复杂度 O(1)。

最坏情况时间复杂度就是，在最糟糕的情况下，执行这段代码的时间复杂度。就像上面的示例，如果数组中没有要查找的变量x，需要把整个数组都遍历一遍才行，所以这种最糟糕 情况下对应的时间复杂度就是最坏情况时间复杂度 O(n)。

最好情况时间复杂度和最坏情况时间复杂度对应的都是极端情况下的代码复杂度，发 生的概率其实并不大。为了更好地表示平均情况下的复杂度，就出现了平均情况时间复杂度的概念。那平均情况时间复杂度如何分析呢？以上面的那段代码为例。

要查找的变量 x在数组中的位置，有 n+1 种情况：在数组的 0～n-1 位置中和不在数组中。把每种情况下，查找需要遍历的元素个数累加起来，然后再除以 n+1，就可以得到需要遍历的元素个 数的平均值，即：

在上面的学习中，我们知道时间复杂度的大O标记法中，可以省略掉系数、低阶、常量，所以，咱们把刚刚这个公 式简化之后，得到的平均时间复杂度就是 O(n)。

空间复杂度分析

空间复杂度相对时间复杂度来说就简单很多了，空间复杂度也不是用来计算程序实际占用的空间的。空间复杂度是对一个算法在运行过程中临时占用存储空间大小的一个量度。空间复杂度比较常用的有：O(1)、O(n)、O(n²)，我们一起来看看这几种常用的空间复杂度。

空间复杂度 O(1)

空间复杂度 O(1) 说明临时开辟的内存空间跟变量n没有关系，不会随着n的变化而变化。例如下面这段代码。

public void sum(int n) {
    int sum = 0;
    for (int i = 1; i <= n; i++) {
        sum += i;
    }
    System.out.println(sum);
}

虽然上面的这段代码有变量n，但是在循环的时候并没有开辟新的内存空间。所以这是的空间复杂度为 O(1)。

空间复杂度 O(n)

空间复杂度为 O(n) 说明在执行代码的过程中，开辟的临时空间大小跟n成正比的关系，例如下面这段代码.

public void array(int n) {
    int[] array = new int[n];
    for (int i = 1; i <= n; i++) {
        array[i] = i;
    }
}

这段代码中新new了一个大小为n的array数组，所以这段代码的空间复杂度为O(n)。

空间复杂度 O(n²)

空间复杂度 O(n²) 就是在代码的执行过程中新开辟了一个二维列表，如下面这段代码。

public void array(int n) {
    int[][] array = new int[n][n];
    for (int i = 1; i <= n; i++) {
        for (int j=0;j<n;j++) {
            array[i][j] = j;
        }
    }
}

文章不足之处，望大家多多指点，共同学习，共同进步

最后

打个小广告，欢迎扫码关注微信公众号：「平头哥的技术博文」，一起进步吧。

平头哥的技术博文

参考资料

• 数据结构与算法之美(极客时间)