算法/数据结构|数据结构与算法_01_时间复杂度和空间复杂度算法

数据结构与算法，系列文章传送地址，请点击本链接。
目录

一、为什么需要复杂度分析？
二、大 O 复杂度表示法
三、时间复杂度分析的方法
四、几种常见时间复杂度实例分析
五、空间复杂度分析
六、最好、最坏情况时间复杂度
七、平均情况时间复杂度
八、均摊时间复杂度

一、为什么需要复杂度分析？时间、空间复杂度是衡量你编写算法代码执行效率的考量指标。
你可能会有些疑惑，我把代码跑一遍，通过统计、监控，就能得到算法执行的时间和占用的内存大小。为什么还要做时间、空间复杂度分析呢？这种分析方法能比我实实在在跑一遍得到的数据更准确吗？很显然这种事后统计的方法时可行的，但是会存在一定的局限性，主要体现在如下几点：
1、测试结果非常依赖测试环境（不同的硬件环境对统计结果的影响很大）
2、测试结果受数据规模的影响很大（由于选取的样例数据很难包罗万象，那么数据规模过小或者过大都可能影响测试的结果。而且不同规模的数据，在不同的算法上还会体现出不同的效果）
因此，我们需要一种不依赖测试数据的一种粗略度量方式。这也就是本文所讲的复杂度分析法；
二、大 O 复杂度表示法算法的执行效率，粗略地讲，就是算法代码执行的时间。但是，如何在不运行代码的情况下，用“肉眼”得到一段代码的执行时间呢？

文章图片

具体解释一下这个公式。其中，T(n) 它表示代码执行的时间；n 表示数据规模的大小；f(n) 表示每行代码执行的次数总和。因为这是一个公式，所以用 f(n) 来表示。公式中的 O，表示代码的执行时间 T(n) 与 f(n) 表达式成正比。
大 O 时间复杂度实际上并不具体表示代码真正的执行时间，而是表示代码执行时间随数据规模增长的变化趋势，所以，也叫作渐进时间复杂度，简称时间复杂度。当 n 很大时，你可以把它想象成 10000、100000。而公式中的低阶、常量、系数三部分并不左右增长趋势，所以都可以忽略。我们只需要记录一个最大量级就可以了。
三、时间复杂度分析的方法 1. 只关注循环执行次数最多的一段代码
大 O 这种复杂度表示方法只是表示一种变化趋势。我们通常会忽略掉公式中的常量、低阶、系数，只需要记录一个最大阶的量级就可以了。所以，我们在分析一个算法、一段代码的时间复杂度的时候，也只关注循环执行次数最多的那一段代码就可以了。这段核心代码执行次数的 n 的量级，就是整段要分析代码的时间复杂度。如：当复杂度为O(2n+1)时，我们可以简化为O(n)
2. 加法法则：总复杂度等于量级最大的那段代码的复杂度
总的时间复杂度就等于量级最大的那段代码的时间复杂度。那我们将这个规律抽象成公式就是：如果 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. 乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积
同理乘法法则就为：
如果 T1(n)=O(f(n))，T2(n)=O(g(n))；那么 T(n)=T1(n)*T2(n)=O(f(n))*O(g(n))=O(f(n)*g(n)).
如：假设 T1(n) = O(n)，T2(n) = O(n2)，则 T1(n) * T2(n) = O(n3)。落实到具体的代码上，我们可以把乘法法则看成是嵌套循环。
四、几种常见时间复杂度实例分析
文章图片

对于上述的复杂度量级，可以粗略地分为两类，多项式量级和非多项式量级。其中，非多项式量级只有两个：O(2n) 和 O(n!)。
当数据规模 n 越来越大时，非多项式量级算法的执行时间会急剧增加，求解问题的执行时间会无限增长。所以，非多项式时间复杂度的算法其实是非常低效的算法。
按照数据图例相应复杂度的增长曲线如下：

文章图片

1. O(1)
O(1) 只是常量级时间复杂度的一种表示方法，并不是指只执行了一行代码。比如这段代码，即便有 3 行，它的时间复杂度也是 O(1），而不是 O(3)。只要代码的执行时间不随 n 的增大而增长，这样代码的时间复杂度我们都记作 O(1)。或者说，一般情况下，只要算法中不存在循环语句、递归语句，即使有成千上万行的代码，其时间复杂度也是Ο(1)。
2. O(logn)、O(nlogn)
对数阶时间复杂度，一般是是循环中出现了一定的跳远，形成等比数，比如下面的代码：

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

从代码中可以看出，变量 i 的值从 1 开始取，每循环一次就乘以 2。当大于 n 时，循环结束。还记得我们高中学过的等比数列吗？实际上，变量 i 的取值就是一个等比数列。所以，我们只要知道 x 值是多少，就知道这行代码执行的次数了。通过 2x=n 求解 x 这个问题我们想高中应该就学过了，我就不多说了。x=log2n，所以，这段代码的时间复杂度就是 O(log2n)。由于采用大O计数法，忽略系数，那么就是O(logn)的时间复杂度了。同理，如果上面代码中不是乘以2，而是乘以3，同样是O(logn)的时间复杂度.
那么，如果O(logn)的时间复杂度又执行了n次，那么就是O(nlogn)了。，O(nlogn) 也是一种非常常见的算法时间复杂度。比如，归并排序、快速排序的时间复杂度都是 O(nlogn)。
3. O(m+n)、O(m*n)
当代码的复杂度由两个数据的规模来决定，如：m 和 n 是表示两个数据规模。我们无法事先评估 m 和 n 谁的量级大，所以我们在表示复杂度的时候，就不能简单地利用加法法则，省略掉其中一个。所以，上面代码的时间复杂度就是 O(m+n)。示例代码：

int cal(int m, int n) {
int sum_1 = 0;
int i = 1;
for (; i < m; ++i) {
sum_1 = sum_1 + i;
}

int sum_2 = 0;
int j = 1;
for (; j < n; ++j) {
sum_2 = sum_2 + j;
}

return sum_1 + sum_2;
}

针对这种情况，原来的加法法则就不正确了，我们需要将加法规则改为：T1(m) + T2(n) = O(f(m) + g(n))。但是乘法法则继续有效：T1(m)*T2(n) = O(f(m) * f(n))。
五、空间复杂度分析时间复杂度的全称是渐进时间复杂度，表示算法的执行时间与数据规模之间的增长关系。类比一下，空间复杂度全称就是渐进空间复杂度（asymptotic space complexity），表示算法的存储空间与数据规模之间的增长关系。常见的空间复杂度就是 O(1)、O(n)、O(n2 )
六、最好、最坏情况时间复杂度首先我们来看个案例，我们从一个数组array中查找第一个为x的数位置，如果这个数在第array[0] 位置，那么我们时间复杂度就是O(1),如果在最后一位array[n-1]中，那么就是O(n)了。所以，不同的情况下，一段代码的时间复杂度是不一样的。示例代码如下：

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

顾名思义，最好情况时间复杂度就是，在最理想的情况下，执行这段代码的时间复杂度。就像我们刚刚讲到的，在最理想的情况下，要查找的变量 x 正好是数组的第一个元素，这个时候对应的时间复杂度就是最好情况时间复杂度。
同理，最坏情况时间复杂度就是，在最糟糕的情况下，执行这段代码的时间复杂度。就像刚举的那个例子，如果数组中没有要查找的变量 x，我们需要把整个数组都遍历一遍才行，所以这种最糟糕情况下对应的时间复杂度就是最坏情况时间复杂度。
七、平均情况时间复杂度接着上面的案例，要查找的变量 x 在数组中的位置，有 n+1 种情况：在数组的 0～n-1 位置中和不在数组中。我们把每种情况下，查找需要遍历的元素个数累加起来，然后再除以 n+1，就可以得到需要遍历的元素个数的平均值，即：

文章图片

时间复杂度的大 O 标记法中，可以省略掉系数、低阶、常量，所以，咱们把刚刚这个公式简化之后，得到的平均时间复杂度就是 O(n)。
另外，如果我们考虑到由于上面n+1的情况出现的概率不同情况，那么，要查找的变量 x，要么在数组里，要么就不在数组里。这两种情况对应的概率统计起来很麻烦，为了方便你理解，我们假设在数组中与不在数组中的概率都为 1/2。另外，要查找的数据出现在 0～n-1 这 n 个位置的概率也是一样的，为 1/n。所以，根据概率乘法法则，要查找的数据出现在 0～n-1 中任意位置的概率就是 1/(2n)。
因此，前面的推导过程中存在的最大问题就是，没有将各种情况发生的概率考虑进去。如果我们把每种情况发生的概率也考虑进去，那平均时间复杂度的计算过程就变成了这样：

文章图片

这个值就是概率论中的加权平均值，也叫作期望值，所以平均时间复杂度的全称应该叫加权平均时间复杂度或者期望时间复杂度。
引入概率之后，前面那段代码的加权平均值为 (3n+1)/4。用大 O 表示法来表示，去掉系数和常量，这段代码的加权平均时间复杂度仍然是 O(n)。
八、均摊时间复杂度均摊时间复杂度就是一种特殊的平均时间复杂度，两个条件满足时使用：
1）代码在绝大多数情况下是低级别复杂度，只有极少数情况是高级别复杂度；
2）低级别和高级别复杂度出现具有时序规律。均摊结果一般都等于低级别复杂度。

声明：文章内容是极客时间专栏学习的学习笔记，会做简化或调整，欢迎大家留言和评论。
【算法/数据结构|数据结构与算法_01_时间复杂度和空间复杂度】数据结构与算法，系列文章传送地址，请点击本链接。