2022-08-26  2022-09-01    3613 字  8 分钟

i.e. Intro to Algorithms

(。・∀・)ノ゙嗨,我是 Carrie Anne,欢迎收看计算机科学速成课!

前两集,我们"初尝"了高级编程语言(比如 Python 和 Java),我们讨论了几种语句 - 赋值语句,if 语句,循环语句,以及把代码打包成 “函数”,比如算指数。重要的是,之前写的指数函数只是无数解决方案的一种,还有其它方案 - 用不同顺序写不同语句 也能得到一样结果。

不同的是 “算法”,意思是:解决问题的具体步骤,即使结果一致,有些算法会更好。一般来说,所需步骤越少越好,不过有时我们也会关心其他因素,比如占多少内存。

“算法” 一词来自 波斯博识者 阿尔·花拉子密, 1000 多年前的代数之父之一 ,如何想出高效算法 - 是早在计算机出现前就有的问题,诞生了专门研究计算的领域,然后发展成一门现代学科。

你猜对了!计算机科学!

记载最多的算法之一是"排序",比如给名字、数字排序。排序到处都是,找最便宜的机票、按最新时间排邮件、按姓氏排联系人,这些都要排序。你可能想"排序看起来不怎么难… 能有几种算法呢?“答案是超多!

计算机科学家花了数十年发明各种排序算法。还起了酷酷的名字,“冒泡排序” (Bubble Sort)、“意面排序”(Spaghetti Sort),我们来试试排序!

试想有一堆机票价格,都飞往印第安纳波利斯 (美国地名),数据具体怎么在内存中表示 下周再说。

上图的这样一组数据 叫"数组”(Array)。

来看看怎么排序,先从一种简单算法开始。

- 先找到最小数,从最上面的 307 开始,因为现在只看了这一个,所以它是最小数
- 下一个是 239,比 307 小,所以新的最小数变成 239
- 下一个是 214 ,新的最小数
- 250 不是,384, 299, 223, 312 都不是
- 现在扫完了所有数字,214 是最小的
- 为了升序排列(从小到大排序),把 214 和最上面的数字,交换位置

好棒!刚排序了一个数字!现在重复同样的过程!

- 这次不从最上面开始,从第 2 个数开始,先看到 239,我们当作是 "最小数"
- 扫描剩下的部分,发现 223 最小,所以把它和第 2 位交换
- 重复这个过程,从第 3 位数字开始,让 239 和 307 互换位置
- 重复直到最后一个数字

瞧,数字排好了,可以买机票了!

刚刚这种方法,或者说算法,叫 选择排序 - 非常基础的一种算法。

以下是"伪代码"(pseudo-code)。

这个函数可以排序 8 个,80 个或 8 千万个数字,函数写好了就可以重复使用,这里用循环遍历数组,每个数组位置都跑一遍循环,找最小数然后互换位置。可以在代码中看到这一点 (一个 for 循环套另一个 for 循环),这意味着,大致来说,如果要排 N 个东西,要循环 N 次,每次循环中再循环 N 次,共 N*N 。

算法的 输入大小 和 运行步骤 之间的关系,叫算法的 复杂度 ,表示运行速度的量级。计算机科学家们把算法复杂度叫 - 没开玩笑 - 大 O 表示法 。

算法复杂度 O(N) 效率不高。前面的例子有 8 个元素(n=8), 8 = 64,如果 8 个变 80 个,运行时间变成 80 = 6400,虽然大小只增长了 10 倍(8 到 80),但运行时间增加了 100 倍!(64 到 6400 )。随着数组增大,对效率的影响会越来越大,这对大公司来说是个问题,比如 谷歌,要对几十亿条信息排序。

作为未来的计算机科学家你可能会问:有没有更高效的排序算法?

回到未排序的数组,试另一个算法 “归并排序”。

- 第一件事是检查数组大小是否 > 1
- 如果是,就把数组分成两半
- 因为数组大小是 8,所以分成两个数组,大小是 4
- 但依然大于 1,所以再分成大小是 2 的数组
- 最后变成 8 个数组,每个大小为 1
- 现在可以"归并"了,"归并排序"因此得名
- 
- 从前两个数组开始,读第一个(也是唯一一个)值
- 307 和 239
- 239 更小,所以放前面
- 剩下的唯一数字是 307 ,所以放第二位
- 成功合并了两个数组

重复这个过程,按序排列,然后再归并一次。

- 同样,取前两个数组,比较第一个数
- 239 和 214 
- 214 更小,放前面
- 
- 再看两个数组里的第一个数:239 和 250
- 239 更小,所以放下一位
- 
- 看剩下两个数:307 和 250
- 250 更小,所以放下一位
- 
- 最后剩下 307 ,所以放最后
- 
- 每次都以 2 个数组开始
- 然后合并成更大的有序数组

我们把刚隐藏起来的,下面的数组也这样做。

现在有两个大小是 4 的有序数组,就像之前,比较两个数组的第一个数,取最小数,重复这个过程,直到完成,就排好了!

但坏消息是:无论排多少次,你还是得付 214 美元到 印第安纳波利斯。总之,“归并排序"的算法复杂度是 O(n * log n),

  • n 是需要 比较+合并 的次数,和数组大小成正比
  • log N 是合并步骤的次数

例子中把大小是 8 的数组,分成四个数组,然后分成 2 个,最后分成 1 个,分了 3 次。重复切成两半,和数量成对数关系

相信我!

Log_2 8=3

如果数组大小变成 16 - 之前的两倍,也只要多分割 1 次,因为 Log_2 16=4 ,即使扩大一千倍,从 8 到 8000,分割次数也不会增大多少 - log_2 8000≈13 ,13 比 3 只是 4 倍多一点,然而排序的元素多得多,因此"归并排序"比"选择排序"更有效率。

这下我收藏的陶瓷猫 可以更快排序了!

有好几十种排序算法,但没时间讲。

所以我们来谈一个经典算法问题:图搜索(graph search)。

“图” 是用线连起来的一堆 “节点”,可以想成地图,每个节点是一个城市,线是公路。一个城市到另一个城市,花的时间不同,可以用 成本 (cost) 或 权重 (weight) 来代称,代表要几个星期。假设想找"高庭"到"凛冬城"的最快路线,最简单的方法是尝试每一条路,计算总成本,这是蛮力方法。假设用蛮力方法 来排序数组,尝试每一种组合,看是否排好序,这样的时间复杂度是 O(n!),n 是节点数,n! 是 n 乘 n-1 乘 n-2… 一直到 1,比 O(n ) 还糟糕。

我们可以更聪明些!

图搜索问题的经典算法发明者是理论计算机科学的伟人 Edsger Dijkstra,所以叫 “Dijkstra 算法”。从"高庭"开始,此时成本为 0,把 0 标在节点里,其他城市标成问号,因为不知道成本多少,Dijkstra 算法总是从成本最低的节点开始,目前只知道一个节点 “高庭”, 所以从这里开始,跑到所有相邻节点,记录成本,完成了一轮算法,但还没到"凛冬城”,所以再跑一次 Dijkstra 算法,“高庭” 已经知道了,下一个成本最低的节点,是 “君临城”。就像之前,记录所有相邻节点的成本,到"三叉戟河"的成本是 5,然而我们想记录的是,从"高庭"到这里的成本,所以"三叉戟河"的总成本是 8+5=13 周,现在走另一条路到"奔流城",成本高达 25 ,总成本 33,但 “奔流城” 中最低成本是 10,所以无视新数字,保留之前的成本 10,现在看了"君临城"的每一条路,还没到"凛冬城" 所以继续。下一个成本最低的节点,是"奔流城",要 10 周,先看 “三叉戟河” 成本: 10+2=12,比之前的 13 好一点,所以更新 “三叉戟河” 为 12,“奔流城"到"派克城"成本是 3,10+3=13,之前是 14,所以更新 “派克城” 为 13。“奔流城"出发的所有路径都走遍了, 你猜对了,再跑一次 Dijkstra 算法。下一个成本最低的节点,是"三叉戟河”,从"三叉戟河"出发,唯一没看过的路,通往"凛冬城”!成本是 10,加"三叉戟河"的成本 12,总成本 22。再看最后一条路,“派克城"到"凛冬城”,成本 31。现在知道了最低成本路线,让军队最快到达,还绕过了"君临城"!

Dijkstra 算法的原始版本,构思于 1956 年,算法复杂度是 O(n )。前面说过这个效率不够好,意味着输入不能很大,比如美国的完整路线图,幸运的是,Dijkstra 算法几年后得到改进,变成 O(n log n + l)。

> n 是节点数,l 是多少条线

虽然看起来更复杂,但实际更快一些。用之前的例子,可以证明更快(6 个节点 9 条线),从 36 减少到 14 左右。

就像排序,图搜索算法也有很多,有不同优缺点。每次用谷歌地图时,类似 Dijkstra 的算法就在服务器上运行,找最佳路线,算法无处不在,现代世界离不开它们。

这集只触及了算法的冰山一角。

但成为计算机科学家的核心,是根据情况合理决定 用现有算法 还是自己写新算法。

希望这集的小例子能让你体会到这点。

下周见。