数据结构和算法本身解决的是“快”和“省”的问题，即如何让代码运行得更快，如何让代码更省存储空间。所以，执行效率是算法一个非常重要的考量指标。那如何来衡量你编写的算法代码的执行效率呢？这就要用到时间、空间复杂度分析了

为什么需要复杂度分析？

在代码写完后，我们把代码跑一遍，通过统计、监控，就能得到算法执行的时间和占用的内存大小。为什么还要做时间、空间复杂度分析呢？这种分析方法能比我实实在在跑一遍得到的数据更准确吗？

这种评估执行效率的方法是没有问题的，但是这种【事后统计法】具有很大的局限性。

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

    测试环境中硬件的不同会对测试结果有很大的影响。你在 i9 主机处理器上跑的代码和在树莓派上跑的代码，绝大部分结果应该都是前者更快。还有，比如原本在这台机器上 a 代码执行的速度比 b 代码要快，等换到另一台机器上时，可能会有截然相反的结果。

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

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

所以，我们需要一个不用具体的测试数据来测试，就可以粗略地估计算法的执行效率的方法，这就是时间、空间复杂度分析。

大 O 复杂度表示法

算法的执行效率，粗略地讲，就是算法代码执行的时间。但是，如何在不运行代码的情况下，用“肉眼”得到一段代码的执行时间呢？这里有段非常简单的代码，求 1,2,3…n 的累加和。现在来估算一下这段代码的执行时间吧

1
2
3
4
5
6
7
8
int cal(int n) {
   int sum = 0;
   int i = 1;
   for (; i <= n; ++i) {
     sum = sum + i;
   }
   return sum;
}

假设每行代码执行的时间都一样，为 unit_time。在这个假设的基础之上，第 2、3 行代码分别需要 1 个 unit_time 的执行时间，第 4、5 行都运行了 n 遍，所以需要2n*unit_time 的执行时间，所以这段代码总的执行时间就是 (2n+2)*unit_time。可以看出来，所有代码的执行时间 T(n) 与每行代码的执行次数成正比。

按照这个分析思路，我们再来看这段代码。

1
2
3
4
5
6
7
8
9
10
11
int cal(int n) {
   int sum = 0;
   int i = 1;
   int j = 1;
   for (; i <= n; ++i) {
     j = 1;
     for (; j <= n; ++j) {
       sum = sum +  i * j;
     }
   }
}

依旧假设每个语句的执行时间是 unit_time。那这段代码的总执行时间 T(n) 是多少呢？

第 2、3、4 行代码，每行都需要 1 个 unit_time 的执行时间，第 5、6 行代码循环执行了 n 遍，需要 2n unit_time 的执行时间，第 7、8 行代码循环执行了 n2 遍，所以需要 2n2 unit_time 的执行时间。所以，整段代码总的执行时间 T(n) = (2n2+2n+3)*unit_time。

尽管我们不知道 unit_time 的具体值，但是通过这两段代码执行时间的推导过程，我们可以得到一个非常重要的规律，那就是，所有代码的执行时间 T(n) 与每行代码的执行次数 n 成正比。

我们可以把这个规律总结成一个公式：T(n)=O(f(n) )

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

所以，第一个例子中的 T(n) = O(2n+2)，第二个例子中的 T(n) = O(2n2