小蝠猫学算法#3——算法效率度量

文章寄语

mi promesas trovi vin,do ankaŭ vi, bonvolu ne plu dubu.(我一定会找到你，所以也请你，不要再怀疑。)
　　　　　　　　　　　　　　　　　　　　—— <<星灵感应>>

---

引言

数据结构笔记第三篇。算法效率的度量[考纲有此内容]

知识点大致按照《Hello!算法》书籍进行。因为数据结构与算法在非常多的考试中都有。

本人自知学疏才浅，一定有许多错误，恳请批评指正。

下面是几个上述提到的链接：

《Hello!算法》网页版 全国计二级官网 洛谷官网-刷题可用

星空如此灿烂，灯塔与之响应。出发吧

---

第三节 时间和空间复杂度

时间复杂度

时间增长趋势

时间复杂度就是评估某段代码运行时间的东西。且一个语句的频度,”频”即该语句被重复执行的次数。

比如现在我有三个循环，A只循环一次，B循环n次(未知)，C循环1000次。怎么判断这三者的时间复杂度？

很简单，可以(我的拙劣理解,实际上是不对的)使用高数中极限的概念理解 ，具体如下：

• A的时间复杂度为: 极限结果不受n影响，不管n取多少都是1，称之 “常数阶” 复杂度。
• B的时间复杂度为: 极限结果受n影响，n取值越大结果就越大，称之 “线性阶” 复杂度。
• C的时间复杂度为: 极限结果不受n影响，不管n取多少都是1000，称之 “常数阶” 复杂度。

从这里就可以看到，只要n的取值大于1000，常数阶复杂度一定优于线性阶的。同时，AC其实是相同复杂度，但如果要较真的话，A比C更优。

函数渐进上界

书籍里那个什么渐进上界我一点看不明白，我还以为是高数里函数有界性的那个上界。但是没看懂不要紧。

只需要明白复杂度的符号是一个大O，记作O(复杂度),这个就是那个什么渐进上界。

然后针对特定代码，就像下面这段书上给的：

void algorithm(int n) {
    //以下语句一共操作了3次
    int a = 1;  
    a = a + 1;  
    a = a * 2;  
    //一次循环均有i++和输出操作，一共2n次
    for (int i = 0; i < n; i++) { 
        cout << 0 << endl;  
    }
}

所以这段代码一共操作了次,操作数用T(n)表示，所以操作数一共是:

然后使用极限，因为是趋于无穷，可以看成这样：

抓大头就是挑出次数最高的就好了，所以代码时间复杂度是

因为系数2不确定(即为c)，他可以取任意大小，所以舍弃。所以最终的结果即为 ,这就是”线性阶”复杂度。

仔细一想，为什么可以用”抓大头”呢？因为我们取得是中，增长速度最快的项。即最深度循环。

拿上面的[2n+3]举例，总有这个式子成立：

这个像是废话，但是如果后者的名字叫上界函数呢？函数有界性x

函数渐进上界定义

若存在正实数和实数,使得对于所有的,均有，则可认为给出了的一个渐近上界,记为

函数渐进上界图像

其实还可以用函数极限理解(?)

• 这段话里，函数的渐进上界为

这个函数极限的结果必须要存在，(因为函数极限存在必定有界),怎么办呢？抓出的最高次项，然后去掉系数即可。

比如有一块代码，他的总操作次数为,根据”抓大头”,这个函数的渐进上界就为。

因为在n趋向于无穷的时候，总有，因为3为系数c，系数c忽略不计，所以这个代码的时间复杂度即为。

时间推算方法

注意：

• 不管真的是数学也好，程序代码也好。在判断项和”抓大头”的时候，判断的从来都是这几个项的增长趋势。增长趋势不会受系数c和加减常数影响。

推算方法回顾:

• ①因为代码一般较为复杂，一个一个算再提取会非常慢。所以忽略所有不带未知数(即常数)的步骤。
• ②因为系数c是可以不断变化的，上面也说了增长趋势不会受系数c和加减常数影响,所以所有系数也都可以忽略。
• ③套娃使用乘法，类似n(n)这样。不套娃使用加法
• ④使用 “抓大头*”。注意，”抓大头”法的未知数n是趋于无穷大的，需要在无穷大时比较其大小。

所以在趋向于无穷时，从低到高顺序分别为：常数阶 < 对数阶 < 线性阶 < 线性对数阶 < 平方阶 < 指数阶 < 阶乘阶。

常见复杂度类型

1. 常数阶

因为不包含未知数，n不管取多大也与其无关，其始终是一个固定的常数。复杂度最小，代码此时最优，耗时最短。

虽然有些时候看起来大，比如操作数是100000等。但是系数c(即100000)不是可以省略的嘛，前者就会变成，也就是。

哈希表的增删查均为O(1)

2. 线性阶

常见于循环结构里，遍历每一个元素的情况。且没有循环套娃的情况。复杂度为。

因为包含未知数n，在操作数趋于无穷的情况下，这个时间肯定是比常数阶大的，所以复杂度和耗时比常数阶高。

未知数n根据实际输入或数组/链表的规模决定

3. 平方阶

常见于循环套娃的情况，两层娃即n(n) ->,三层娃即n(n(n)) ->。实际上，这个复杂度是,α是套娃的层数。

第一篇做迭代和递归的笔记时候说过套娃操作数不一样的情况。比如内层循环是, 外层循环是。那套娃相乘，操作数即为.

直接”抓大头”，得，因为系数c和常数操作均可省略，结果为。不管内外层怎么限制，都是这个。

比线性阶耗时更大并更复杂。因为幂函数的特性，高次方的情况下操作数也是会和指数阶和阶乘阶一样爆炸的。

未知数n根据实际输入或数组/链表的规模决定。多维数组少用

4. 指数阶

指数爆炸！例子是细胞分裂(书上的例子)。每次乘以2。第一次2个，第二次4个，第三次8个，依次递增。

所以操作总数就为: (递归树的总节点数)

• 等比数列求和公式:

上式化简后(等比数列求和),结果为,因为第一项的1不符合等比数列，最后补加上。因为常数操作一般省略，所以最终为

因为指数爆炸的特性。指数阶复杂度第二大，耗时也第二长，算是老二，因为老大更重量级。应当避免使用指数阶复杂度

多在递归和穷举法中使用。数据量较小时可以使用，数据量大时千万别用

5. 对数阶

和指数阶相反，对数阶是每次除以2。第一次8个，第二次4个，第三次2个，依次递减。

多见于分治。因为每次除以二，不管未知数n是多少，操作到只有2个的步数都是 (看未知数能除多少个2)。最后还有一步，因为需要操作到只剩一个才停止。

总操作数为：,因为常数操作省略，最终复杂度为。

• 不一定除以2，可以除其他的数字，这个底数相当于也是系数，可以省略。即复杂度。至于换底公式，书上说底数可以在不影响复杂度的前提下随意转换。

多在分治中使用。仅次于常数级复杂度，优秀耗时少

6. 线性对数阶

凡是个东西都可以套娃，线性对数阶也是套娃套来的。

但树只有一棵，对数之间套不了；指数和平方本来就大，还套个锤头。所以对数最多只能套娃套个线性n。

相乘就好了。常见于排序算法。

多在主流排序算法中使用。较为优秀耗时也较少

7. 阶乘阶

阶乘用于解决”数字全排列”问题。他是递归的，递归就意味着套娃，意味着计算总排列是用乘法而不是加法。

这就是重量级的一点，他用乘法不是加法。所以未知数n的操作总数为:

我用以下例子来表明老大和老二的区别：

• 当规模n取20时，指数阶的操作数为
• 当规模n取20时，阶乘阶的操作数为

一眼定真假，阶乘的操作很恐怖，比指数爆炸还恐怖。所以不要使用阶乘阶复杂度，除非数据量特别小。

最高的复杂度，最大的耗时——正在奏响mvp凯歌<有为算法>

最差/最佳/平均时间复杂度

我在前面的函数渐进上界写过，关于的复杂度是必须要存在的。而且函数极限，极限存在是必定有界的。

有界是两个界，有渐进上界了，那肯定有渐进下界。

上界嘛，在某个值时函数图像上所有点都小于这个值，相当于下限，也就是最坏情况下的操作数。函数图像上没有点会比这个值更差了。称作最差时间复杂度，记为。

相反，下界就是在某个值时函数图像上所有点都大于这个值，为上限，也就是最佳情况下的操作数。称作最佳时间复杂度，记为。

• 我们常用的严谨来讲其实应该写成,称作平均时间复杂度。即算法期望运行时间(即原始的)

一般总是考虑最坏情况下的时间占用，所以我们日常用的都是最差时间复杂度，给其框定时间的”安全”范围。

空间复杂度

代码空间和推算方法

时间复杂度看输入，空间复杂度不看输入。只看开辟了多少空间，用了多少空间，返回了多少空间。书籍名词是暂存数据、栈帧空间和输出数据。图片如下:

算法空间

时间复杂度看平均，空间复杂度看最差。只需要分析除了输入和程序以外的额外空间。

**原地算法指在原来的基础上操作，不用作为辅助的空间。即常数阶。

int func() {
    // 已经有返回值return 0
    return 0;
}
/* 循环的空间复杂度为 O(1) */
void loop(int n) {
    for (int i = 0; i < n; i++) {
        func();
    }
}
/* 递归的空间复杂度为 O(n) */
void recur(int n) {
    //直到n=1之前都没有返回return
    if (n == 1) return;
    return recur(n - 1);
}

递归函数统计栈帧空间,我的理解就是判断和统计每一层是否已经返回值。一次循环如果已经返回值了，会释放空间。就和流水线后装满产品的箱子会被运走换上新箱子一样。

如果没有返回值，一次就要算一个未知数n，因为要保存过程直到有返回值；如果有返回值，一次算成一个常数，又因为常数可以忽略，所以有返回值的情况不用算。

常见复杂度类型

从低到高，空间复杂度类型为常数阶 < 对数阶 < 线性阶 < 平方阶 < 指数阶

因为我现在累飞了，写不动笔记了。时间复杂度里面记过了，这里简略地写了。

相对于时间复杂度少几个类型。反过来说，有几个是时间复杂度独有的。

1. 常数阶

一次循环如果已经返回值了，会释放空间。不会积累。空间最优。

常见于和n无关的东西，或者循环中有返回值的调用等。与循环几次无关，因为循环的次数,系数c被省略掉了

2. 线性阶

一次循环如果没有返回值，一次算一个n，因为要保存过程直到有返回值。递归不会中途退出，到最深处才慢慢有返回值。所以运用抓大头和最大值，一般深度多少就使用了多少空间。

数组,列表,栈,队列,哈希表等开一个n大小的就要预留n个位置，开多少就占多少。所以创建就是

常见于和n有关的东西，或者递归

3. 平方阶

数组,列表,栈,队列,哈希表等开一个n大小的就要预留n个位置，开多少就占多少。现在又是套娃，和我的第一篇笔记差不多，把他想象成一个表格，现在不数操作数，数格子，那也是长乘宽。

省略系数c，复杂度为。递归本来就是n，里面再开数组占位置，那相乘也是妥妥

常见于和n有关的东西，并且以套娃形式存在

4. 指数阶

第一篇笔记里就感觉斐波那契的最差情况可能就是满二叉树。确实最差情况是指数阶，但是有点区别。空间最差。

开一个n大小的就要预留n个位置，开多少就占多少。满二叉树也一样的，有多少节点就预留多少位置。又按前文的等比数列求和公式，求出满二叉树一共要开个位置

常见于二叉树，用满二叉树来帮助理解

5. 对数阶

和时间复杂度一样。空间仅次于常数阶。不过形成了 (看n能除多少个2)层的递归树，递归没有直接返回值，深度多少就使用了多少空间。忽略底数即

平衡空间/时间

人总是贪的，希望空间复杂度和时间复杂度都是最低最佳，但是很多情况不可能同时优化，只能优化其中的一个。

这种就得看问题，有”空间换时间”策略和”时间换空间”策略两种策略任君挑选。但是因为时间比金子更宝贵，所以一般抉择都用”空间换时间”策略。数据量大时注意空间就好了。

---

总结

文章结语

人类把最精密的保密系统，都用在了自我毁灭上。
　　　　　　　　　　　　　　　　　　　　——流浪地球2

---

笔记完毕 编辑完毕时间CST 6.30 01:10

最后修改于8.15 23:15