数据结构与算法复杂度详解

可以看见我们跑通了 37 个用例，但是在某一个用例时，超出了时间限制，这是什么原因导致的呢？ 我们可以看看这题给出的提示

如果给出的数组非常大，里面存放了很多的数据，同时要轮转 90 次，这时就会超出时间的限制。 那么，如何衡量其好与坏呢？为此我们需要引入复杂度的概念。

复杂度概念

算法在编写成可执行程序后，运行时需要耗费时间资源和空间 (内存) 资源。 因此衡量⼀个算法的好坏，⼀般是从时间和空间两个维度来衡量的，即时间复杂度和空间复杂度。

时间复杂度主要衡量⼀个算法的运行快慢，而空间复杂度主要衡量⼀个算法运行所需要的额外空间。

3. 时间复杂度

定义：在计算机科学中，算法的时间复杂度是⼀个函数式 T(N)，它定量描述了该算法的运行时间。时间复杂度是衡量程序的时间效率，那么为什么不去计算程序的运行时间呢？

1. 因为程序运行时间和编译环境和运行机器的配置都有关系，比如同⼀个算法程序，用一个老编译器运行编译和新编译器编译，在同样机器下运行时间不同。
2. 同⼀个算法程序，用一个老低配置机器和新高配置机器，运行时间也不同。
3. 并且时间只能程序写好后测试，不能写程序前通过理论思想计算评估。

这个是我在VS 编译器 x64 位环境下，通过冒泡排序运行 3 次将 100000 排成升序各自所需要的时间，因此我们不去计算程序的运行时间。

那么算法的时间复杂度是⼀个函数式 T(N) 到底是什么呢？这个T(N) 函数式计算了程序的执行次数。在编译链接过程中，我们知道算法程序被编译后生成二进制指令，CPU 执行这些编译好的指令。那么我们通过程序代码或者理论思想计算出程序的执行次数的函数式 T(N)，假设每句指令执行时间基本一样(实际中有差别，但是微乎其微)，那么执行次数时间就是等比正相关，这样也脱离了具体的编译运行环境。执行次数就可以代表程序时间效率的优劣。比如解决⼀个问题的算法 a 程序 T(N) = N，算法 b 程序 T(N) = N^2，那么算法 a 的效率⼀定优于算法 b。

实际中我们计算时间复杂度时，计算的也不是程序的精确的执行次数，精确执行次数计算起来还是很麻烦的 (不同的一句程序代码，编译出的指令条数都是不⼀样的)，计算出精确的执行次数意义也不大，因为我们计算时间复杂度只是想比较算法程序的增长量级，也就是当 N 不断变大时 T(N) 的差别，上⾯我们已经看到了当 N 不断变大时常数和低阶项对结果的影响很小，所以我们只需要计算程序能代表增长量级的大概执行次数，复杂度的表示通常使用大 O 渐进表示法。

3.1 大 O 表示法

什么意思呢？ 我们以上面Func1 为例，T(N)=N^2+2*N+10。 根据大 O 阶第一条规则:只保留最高阶项,O(N)=N^2。

3.2 时间复杂度示例练习

例 1

Func2 执行的基本操作次数： T (N) = 2N + 10 根据推导规则第 3 条得出: Func2 的时间复杂度为：O(N)

例 2

T (N) = M + N 因此：Func2 的时间复杂度为：O(N)

例 3

T (N) = 100 根据推导规则第 1 条得出 Func2 的时间复杂度为：O(1)

例 4

strchr 执行的基本操作次数： （1）若要查找的字符在字符串第一个位置， 则：T (N) = 1 （2）若要查找的字符在字符串最后的⼀个位置， 则：T (N) = N （3）若要查找的字符在字符串中间位置， 则：T (N) =N/2 因此：strchr 的时间复杂度分为： 最好情况：O(1) 最坏情况：O(N) 平均情况：O(N) 由于大 O 表示法一般表示最坏的情况，即O(N)

例 5

（1）若数组有序， 则：T (N) = N, O(N) （2）若数组有序且为降序， 则：T (N) =N ∗ (N + 1)/2, 即 O(N^2) 因此：BubbleSort 的时间复杂度取最差情况为：O(N^2 )

例 6

当 n=2 时，执行次数为 1 当 n=4 时，执行次数为 2 当 n=16 时，执行次数为 4 假设执行次数为 x，则 2x = n 因此执行次数：x = log n 因此：func5 的时间复杂度取最差情况为：O(log2 n)

提问：那么 log2n,logn,lgn 等有区别吗？ 是没有区别的，我们要注意的是增长量级，即变化的 n，无论底数为多少，当 n 越来越大时，这个底数对结果的影响是越来越小的，当 n 趋于无穷时，这个影响可以忽略不计，因此上面几种表示方法都是可以的。

例 7

调用一次 Fac 函数的时间复杂度为 O(1) 而在 Fac 函数中，存在 n 次递归调用 Fac 函数 因此：阶乘递归的时间复杂度为：O(n)

算递归的复杂度的万能公式：创建了多少次函数栈帧 (递推了多少次)*单次递归执行的次数。

4. 空间复杂度

空间复杂度也是⼀个数学表达式，是对⼀个算法在运行过程中因为算法的需要额外临时开辟的空间。 空间复杂度不是程序占用了多少 bytes 的空间，因为常规情况每个对象大小差异不会很大，所以空间复 杂度算的是变量的个数。 空间复杂度计算规则基本跟实践复杂度类似，也使用大 O 渐进表示法。 注意：函数运行时所需要的栈空间 (存储参数、局部变量、⼀些寄存器信息等) 在编译期间已经确定好 了，因此空间复杂度主要通过函数在运行时候显式申请的额外空间来确定。

4.1 空间复杂度示例练习

例 1

BubbleSort 额外申请的空间有 exchange，end 有限个局部变量，使用了常数个额外空间。 因此空间复杂度为 O(1)。

例 2

Fac 递归调用了 N 次，额外开辟了 N 个函数栈帧， 每个栈帧使用了常数个空间 因此空间复杂度为：O(N)

5. 案例扩展

轮转数组

按照思路 1 的方法：经过上面复杂度的学习，我们可以得出其时间复杂度为 O(N^2), 当给的数据过大，轮转次数过多时，势必会造成超过时间限制。

5.1 优化方案 1：采用空间换时间的方法

我们如何将 O(N^2) 的时间复杂度降为 O(N) 呢 (即只嵌套一层循环)?

可以发现这里的空间复杂度为 O(N)，那么是否可以让空间复杂度降为 O(1)，同时又保持时间复杂度为 O(N) 呢？见优化方案 2。

5.2 优化方案 2(优解):

代码看似更复杂了些，但它同时满足了降时间复杂度为 O(N) 和空间复杂度为 O(1)。