数据结构与算法 #时间复杂度 #空间复杂度

前言

路漫漫其修远兮，吾将上下而求索；

一、算法的复杂度

当我们编写了一个 算法之后，如何衡量这个算法到底是好还是坏呢？

• 算法在运行的过程中最重要的指标是此算法快不快以及其在运行的过程之中会消耗多少空间，即时间复杂度与空间复杂度；

时间复杂度：衡量一个算法运行的运行快慢

空间复杂度：衡量一个算法运行时所需要的额外空间

注：在早期计算机的发展中，由于计算机的存储容量小，所以比较关注空间复杂度；但是随着计算机行业的快速发展(摩尔定律：每18个月计算机的硬件便会翻一倍)，内存越来越大并且越来越便宜，于是现在就不那么关注空间复杂度了；

二、时间复杂度

算法的时间复杂度是一个函数，它定量地描述了该算法的运行时间(该算法执行所消耗的时间)；理论来说，时间复杂度是不可能算出来的，只有当此程序在机器上跑起来的时候，才可以知道此算法运行的时间；

注：此处所述的函数，并不是在C语言中的那个函数，而是在数学之中的函数表达式；

时间复杂度为什么不是用来计算该代码运行了多少秒呢？

• 因为并没有一个准确的方式去计算一个算法运行了多少秒；相同的算法在不同的机器上，是有差异的，即一个算法的执行速度受环境的影响；

那么时间复杂度究竟计算的是什么呢？

• 计算的是一个算法之中基本操作(代码)的执行次数；哪个算法的基本操作的执行次数少，那么该算法便会更快；

一个算法花费的时间与其语句的执行次数成正比例，算法中的基本操作的执行次数为算法的时间复杂度；（找到某条基本语句与问题规模N之间的数学表达式）并且在计算的时候也不需要计算该算法精确的执行次数，只需要大概的执行次数便可以了，那么这里便会使用到大O的渐近表示法；

何为大O的渐进表示法？

• 大O符号（Big O notation）: 用于描述函数渐进行为的数学符号

推导大O阶方法：

• 用常数1取代运行时间中的所有加法常数
• 在修改后的运行次数函数中，只保留最高阶项；
• 如果最高阶项存在并且不是1，则去除与这个项目相乘的常数(让最高项的系数为1)

最后所得到的结果便是大O阶；

例子代码如下：

void Func1(int N)
{int i = 0;int j = 0;int k = 0;int count = 0;for (i = 0; i < N; i++){for(j = 0; j < N; j++){count++;}}for(k = 0; k < 2 * N; k++){count++;}int M = 10;while (M--){count++;}printf("%d\n", count);
}

倘若要准确地计算上述代码的执行次数 = N^2 + 2*N + M (其中M为10，是一个常数)

根据推导大O阶规则，则会得到该算法的时间复杂度为：O(N^2) 

从上例，我们可以得知，大O的渐进表示法去掉了那些对结果影响不大的项，保留了对结果影响最大的项(可以采用数学极限的思想)；

计算时间复杂度的技巧：可以大致计算”精确“的，然后再在此基础上利用推导大O阶规则；

另外在有些算法中时间复杂度存在最好、平均、最坏的情况：

最好的情况：任意输入规模的最小运行次数

平均的情况：任意输入规模的期望运行次数

最坏的情况：任意输入规模的最大运行次数

我们在计算一个算法的时间复杂度的时候，一般关注的是其最坏的情况；

三、空间复杂度

空间复杂度也是一个数学表达式，是对一个算法在运行过程中临时额外占用存储空间大小的量度；

空间复杂度并不是精确计算这个程序占用了多少byte 的空间，而是采用大O渐进表达式的方式来计算在运行过程中额外运用了多少空间；

注：函数运行时所需要的栈空间(存储参数、局部变量、一些寄存器的信息等)，在编译期间便已经确定好了，因此空间复杂度主要通过函数在运行的时候显式申请的额外空间来确定的；

换句话说，空间复杂度的计算的是在运行过程中额外占用存储空间的变量个数，倘若在运行的过程中建立栈帧，这也是要算入的；并且遵循推导大O阶的规则；

四、例题

1、例1：冒泡排序

分析：

分析时间、空间复杂度的核心是梳理清楚整个代码的逻辑；

显然冒泡排序的逻辑为：整个冒泡排序会有两个循环，一个控制循环的趟数，一个控制一趟排序之中相邻两元素所要比较的次数，并且每次冒完一趟均会确定好一个元素的最终位置，故而每冒完一趟下一趟冒泡均会减少一次比较；

如此大致看起来，冒泡排序的基本代码执行次数为一个等差数列之和，而复杂度采取的是大O渐进表达式的估算法，即相加的常数项为1，只保留最高项并且最高项的系数为1，显然其时间复杂度变为O(N^2);

而整个冒泡排序的过程都只是在一定大小的数组进行的，并没有使用额外的空间，所以其空间复杂度为O(1)；

2、例2：

分析：

注：大O渐进表达式用的未知数用的是N，有时也可以是M、K等字母；

为什么此处的时间复杂度为O(N+M) ？

• 因为在此处N 与 M 均为未知数，并不知道谁大谁小；按照推导大O阶的方式于是乎便得到了O(N+M);

倘若此处有N 与 M 的大小关系，其时间复杂度便会不同：

而对于此算法的空间复杂度，整个算法的执行依靠的是几个变量，并没有使用额外开辟的空间，故而其空间复杂度为O(1)；

3、例3：

分析：此算法会受其参数的影响，即参数字符串的长度会影响这个算法完成任务所需要的时间；既然字符串的长度不清楚，便可以将字符串的长度看作为N；

当在一个字符串中查找一个字符额时候，可能一上来便找到了，也有可能在中间位置才找到，亦或许在字符串的结尾才能找到……显然会在字符串的哪个位置找到目标字符这也是未知的；

对于时间复杂度来说，关注的使这个算法最坏的情况，故而此算法的时间复杂度为:O(N) ;

呼应上文所述概念：

平均情况有什么特殊意义？

• 大部分算法并不会看其平均情况，即使看平均情况也是看一下这个算法大概会执行多少次；例如，希尔排序，很少出现最坏的情况，并且最坏的情况难以计算，故而希尔排序这个算法会看其平均情况；（其平均情况的计算会使用到一个非常复杂的数学公式进行计算）；

常见的平均情况的计算方式：

1、（最好情况+ 最坏情况）/2

2、按照概率计算(比较复杂)

4、例4: 二分查找

分析：注意二分查找的逻辑；

二分查找会利用到三个指针，一个指向数组的最左，一个指向数组的最右，另外一个指向中间位置；

• 让中间位置的数据与x 相比较，当小于mid 的时候便缩小一半的查找范围，调整left 到mid 右边的位置；倘若大于mid 也会缩小一半的查找范围，调整 right 到 mid 到左边的位置上；而如若mid 所对应得数据等于所要查的数据x ,便代表着查找成功；

显然，我们也不知道所找的数据会在整个数组的哪个位置，存在最好、平均、最坏的情况；二分查找的特性，每次查找没找到便会缩小一半的查找范围，也就是说缩小了几次查找返回便意味着查找了多少次；

最坏的情况就是在这个数组中找不到所找数据，假设我们找了k 次，那么 其中n 为这个数组中元素的个数,由式可得 ： ;所以此算法的时间复杂度为：

当然，由于该二分查找算法并没有使用额外的空间，于是其空间复杂度为:O(1)；

有关二分查找的知识补充：

二分查找的查找效率非常高效，但是这个算法是有缺陷的，即必须在有序数组上才能进行查找；倘若面对所要查找的数据是无序的，那么首先就得排序，然而排序也是一个非常消耗的过程；

于是乎便有了后面的 树 --> 二叉树 --> 搜索二叉树 --> 平衡搜索二叉树 --> AVL Tree 、RBTree(红黑树) ，这些算法，无需排序也可以达到二分查找的高效；以及还有更厉害的哈希表、b树系列.[ps:路漫漫……漫漫路……]

5、例5: 阶乘

分析：递归，便会利用到函数栈帧相关知识来理解；

 递归中基本代码的执行次数 = 递归次数 * 每次递归中基本代码的执行次数(看每次递归中有无循环)；

为什么其空间复杂度为O(N) ？

• 该算法在执行的时候，额外地开辟了空间 -- 函数栈帧的创建；每调用一个函数，便会创建对应的函数栈帧；函数栈帧的开辟个数与递归的次数有关，而在每个函数栈帧中均会使用常数个空间，根据大O渐进表达式的规则，故而其空间复杂度为O(N),图示如下：

递归需要看栈帧的消耗，即看递归的深度；

6、例6: 斐波那契

分析：

显然，斐波那契函数Fib 也遵循: 递归中基本代码的执行次数 = 递归次数 * 每次递归中基本代码的执行次数(看每次递归中有无循环)；

如上图所示，Fib 的递归次数为一个等比数列求和并减去一个X（X为假设缺少的常数个递归次数，远小于前面的等比数列求和的所得值）

根据大O渐进表达式，因为(1+X)远小于 2^n, 所以（1+X）可以忽略，故此算法的时间复杂度为: O(2^N);

 空间复杂度：

同理，递归的空间复杂度看函数栈帧开辟的次数，即递归的深度 再乘以每次递归中额外使用的空间；Fib 的递归深度以大O渐进表达式为：O(2^N) ； 并且每次递归中并没有使用额外的空间，那么Fib 的空间复杂度便为 O(2^N)？

其实不然，因为 2^N 增长地很快，一般情况在Linux 下，建立一个进程的栈，只有8M ；倘若此算法的空间复杂度为 O(2^N) ， 栈肯定会溢出；

实际上，斐波那契函数(递归)是会重复利用空间的，并且不累计；

如上如所示，会先计算一条分支（）然后再计算其他分支；即斐波那契函数再创建栈帧的时候会先建立”一支“的栈帧，直到这一支结束便销毁此支创建的函数栈帧……然后再继续调用下一支以实现重复利用空间；那么此时的计算空间复杂度便是看的递归的深度，即最多创建了多少函数栈帧，故而斐波那契函数的空间复杂度为:O(N)；

注：递归是一条”支路“递归结束返回了再退回去递归另外一条”支路“；

五、常见算法复杂度

常见算法的时间复杂度包括

• 常数时间复杂度(常数阶): O(1)
• 对数时间复杂度(对数阶): O(log n)
• 线性时间复杂度(线性阶): O(n)
• 线性对数时间复杂度(线性对数阶): O(n log n)
• 平方时间复杂度(平方阶): O(n^2)
• 立方时间复杂度(立方阶): O(n^3)
• 指数时间复杂度(指数阶): O(2^n)

总结

1、时间复杂度与空间复杂度的计算基于大O渐进表达式

2、大O符号（Big O notation）: 用于描述函数渐进行为的数学符号

推导大O阶方法：

• 用常数1取代运行时间中的所有加法常数
• 在修改后的运行次数函数中，只保留最高阶项；
• 如果最高阶项存在并且不是1，则去除与这个项目相乘的常数(让最高项的系数为1)

3、分析时间、空间复杂度的核心是梳理清楚整个代码的逻辑；