1 概述
数据结构和算法本身解决的是“快”和“省”的问题，即如何让代码运行得更快，如何让代码更省存储空间。所以，执行效率是算法一个非常重要的考量指标。那如何来衡量你编写的算法代码的执行效率呢？这里就要用到我们今天要讲的内容：时间、空间复杂度分析。
2 为什么需要复杂度分析
把代码跑一遍，通过统计、监控，就能得到算法执行的时间和占用的内存大小。为什么还要做时间、空间复杂度分析呢？因为这种方式可以被认为是:事后统计法
1. 测试结果非常依赖测试环境
测试环境中硬件的不同会对测试结果有很大的影响。比如，我们拿同样一段代码，分别用 Intel Core i9 处理器和 Intel Core i3 处理器来运行，不用说，i9 处理器要比 i3 处理器执行的速度快很多。还有，比如原本在这台机器上 a 代码执行的速度比 b 代码要快，等我们换到另一台机器上时，可能会有截然相反的结果。
2. 测试结果受数据规模的影响很大
对同一个排序算法，待排序数据的有序度不一样，排序的执行时间就会有很大的差别。极端情况下，如果数据已经是有序的，那排序算法不需要做任何操作，执行时间就会非常短。除此之外，如果测试数据规模太小，测试结果可能无法真实地反应算法的性能。比如，对于小规模的数据排序，插入排序可能反倒会比快速排序要快！
所以，我们需要一个不用具体的测试数据来测试，就可以粗略地估计算法的执行效率的方法。
3 时间复杂度
3.1 算法的运行时间
这里有段非常简单的代码,我们来估算一下这段代码的执行时间。
image
① 蓝色框的两条语句，花费两个时间单元
② 黑色框的一条语句，花费n+1个时间单元
③ 红色框的两条语句，花费2*n个时间单元
用T(n)表示这个程序运行了多长时间，那么这个程序运行的时间就可以写成T(n)=3n+3，其中的n被我们称为问题的规模，其实就是你处理问题的大小
3.2 时间复杂度
定义
时间复杂度实际上并不具体表示代码真正的执行时间，而是表示代码执行时间随数据规模增长的变化趋势，所以，也叫作渐进时间复杂度（asymptotic time complexity），简称时间复杂度。可以用以下公式来表示
image
T(n)表示代码执行的时间；n 表示数据规模的大小；f(n) 表示每行代码执行的次数总和。因为这是一个公式，所以用 f(n) 来表示
对于上面的例子我们可以使用T(n)=O(3n+3)来表示，其中这就是大 O 时间复杂度表示法，不过相对于上面的公式，时间复杂度会进行一些简化，
因为时间复杂度一般只关心随着问题规模n趋于无穷时函数中对函数结果影响最大的项，比如说：T(n)=3n+3,当n趋于无穷时，而公式中的低阶、常量、系数三部分并不左右增长趋势，所以都可以忽略。我们只需要记录一个最大量级就可以了，并忽略该项的系数。因此3n+3中应该忽略常量3，并忽略最大量级的系数3，最终时间复杂度表示为O(n).
复杂度量级
image
大小关系
image
简单案例
T(n)=n+1 忽略常量阶 T(n)=n
T(n)=n+n^2 忽略线性阶 T(n)=n^2
T(n)=3n 忽略最高阶的系数 T(n)=n
O(1)常量阶
int i = 8;
int j = 6;
int sum = i + j;
O(1) 只是常量级时间复杂度的一种表示方法，并不是指只执行了一行代码。
比如这段代码，即便有 3 行，它的时间复杂度也是 O(1），而不是 O(3)。
O(logN)对数阶
i=1;
while (i <= n) {
i = i * 2;
}
算法的运行时间T(n)=2LogN+1，忽略常量阶1，以及最高阶系数2，时间复杂度T(n)=O(LogN)
i=1;
while (i <= n) {
i = i * 3;
}
算法的运行时间T(n)= log3n，实际上，不管是以 2 为底、以 3 为底，还是以 10 为底，我们可以把所有对数阶的时间复杂度都记为 O(logn)。
O(n)线性阶
for(int i=0;i<n;i++){
System.out.println("Test")
}
算法的运行时间T(n)=3n+2,忽略常量阶1，以及最高阶系数2，时间复杂度T(n)=O(n)
O(nlogN)线性对数阶
for(int i=0;i<n;i++){
i=1;
while (i <= n) {
i = i * 2;
}
}
时间复杂度T(n)=O(n)*O(logN)=O(nLogN)
O(n^2)平方阶
for(int i=0;i<n;i++){
for(int i=0;i<n;i++){
System.out.println("Test")
}
}
时间复杂度T(n)=O(n)*O(N)=O(n^2).
3.3 时间复杂度分析
只关注循环执行次数最多的一段代码
大 O 这种复杂度表示方法只是表示一种变化趋势。我们通常会忽略掉公式中的常量、低阶、系数，只需要记录一个最大阶的量级就可以了。所以，我们在分析一个算法、一段代码的时间复杂度的时候，也只关注循环执行次数最多的那一段代码就可以了。这段核心代码执行次数的 n 的量级，就是整段要分析代码的时间复杂度。
1 int cal(int n) {
2 int sum = 0;
3 int i = 1;
4 for (; i <= n; ++i) {
5 sum = sum + i;
6 }
7 return sum;
8 }
其中第 2、3 行代码都是常量级的执行时间，与 n 的大小无关，所以对于复杂度并没有影响。循环执行次数最多的是第 4、5 行代码，所以这块代码要重点分析。前面我们也讲过，这两行代码被执行了 n 次，所以总的时间复杂度就是 O(n)。
总复杂度等于量级最大的那段代码的复杂度
int cal(int n) {
int sum_1 = 0;
int p = 1;
for (; p < 100; ++p) {
sum_1 = sum_1 + p;
}
int sum_2 = 0;
int q = 1;
for (; q < n; ++q) {
sum_2 = sum_2 + q;
}
int sum_3 = 0;
int i = 1;
int j = 1;
for (; i <= n; ++i) {
j = 1;
for (; j <= n; ++j) {
sum_3 = sum_3 + i * j;
}
}
return sum_1 + sum_2 + sum_3;
}
这个代码分为三部分，分别是求 sum_1、sum_2、sum_3。我们可以分别分析每一部分的时间复杂度，然后把它们放到一块儿，再取一个量级最大的作为整段代码的复杂度。
第一段的时间复杂度是多少呢？这段代码循环执行了 100 次，所以是一个常量的执行时间，跟 n 的规模无关。
这里我要再强调一下，即便这段代码循环 10000 次、100000 次，只要是一个已知的数，跟 n 无关，照样也是常量级的执行时间。当 n 无限大的时候，就可以忽略。尽管对代码的执行时间会有很大影响，但是回到时间复杂度的概念来说，它表示的是一个算法执行效率与数据规模增长的变化趋势，所以不管常量的执行时间多大，我们都可以忽略掉。因为它本身对增长趋势并没有影响。
那第二段代码和第三段代码的时间复杂度是多少呢？答案是 O(n) 和 O(n2)
那么总时间复杂度为O(n2)
嵌套代码的复杂度等于嵌套内外代码复杂度的乘积
int cal(int n) {
int ret = 0;
int i = 1;
for (; i < n; ++i) {
ret = ret + f(i);
}
}
int f(int n) {
int sum = 0;
int i = 1;
for (; i < n; ++i) {
sum = sum + i;
}
return sum;
}
我们单独看 cal() 函数。假设 f() 只是一个普通的操作，那第 4～6 行的时间复杂度就是，T1(n) = O(n)。但 f() 函数本身不是一个简单的操作，它的时间复杂度是 T2(n) = O(n)，所以，整个 cal() 函数的时间复杂度就是，T(n) = T1(n) * T2(n) = O(n*n) = O(n2)。
4 空间复杂度
定义
时间复杂度的全称是渐进时间复杂度，表示算法的执行时间与数据规模之间的增长关系。类比一下，空间复杂度全称就是渐进空间复杂度（asymptotic space complexity），表示算法的存储空间与数据规模之间的增长关系。
void print(int n) {
int i = 0;
int[] a = new int[n];
for (i; i <n; ++i) {
a[i] = i * i;
}
for (i = n-1; i >= 0; --i) {
print out a[i]
}
}
跟时间复杂度分析一样，我们可以看到，第 2 行代码中，我们申请了一个空间存储变量 i，但是它是常量阶的，跟数据规模 n 没有关系，所以我们可以忽略。第 3 行申请了一个大小为 n 的 int 类型数组，除此之外，剩下的代码都没有占用更多的空间，所以整段代码的空间复杂度就是 O(n)。
参考
极客时间版权所有: https://time.geekbang.org/column/article/40036
网友评论