[OsChina] 好书一起读(85):算法笔记

发表于:1个月前  阅读量:10803

摘要

这阵子看了两本算法书,《算法》和《算法导论》。前一本读着很轻松,内容基本与大学数据结构课程重叠,示例代码用java编写,学习曲线平缓,对应用程序员来说,读它就挺好。后一本我是边看麻省理工的《算法导论》...

这阵子看了两本算法书,《算法》和《算法导论》。

前一本读着很轻松,内容基本与大学数据结构课程重叠,示例代码用java编写,学习曲线平缓,对应用程序员来说,读它就挺好。

后一本我是边看麻省理工的《算法导论》公开课边读的,力不从心,因为我数学基础不好(详下),如果不看数学证明,其内容跟前一本就差不多了,数学基础比较好、对算法感兴趣的朋友,可以尝试之。

强烈建议各公开课平台的学习资源,质量非常高,相见恨晚!足不出户,就能学习名校的课程。但学习时别忘了跟着做习题、做笔记、预习复习。

下面是我的《算法》笔记。

 

零、思想

重中之重。算法真正的精髓。内功心法所在。相比之下,后面讲到的都是具体招式。

内功心法的意义就在,有朝一日你遇到一个没有既有经验的问题,能自己设计出适当的数据结构和算法,而不是只会用别人的轮子。

算法的根本思想,是大问题化为多个小问题,逐渐解决之。(《孙子兵法》:治众如治寡,分数是也;斗众如斗寡,形名是也。)

1.分治

如果能将大问题拆为同性质的小问题,当小到一定程度,能直接解决之。

则采用分治法,递归解决。

2.贪心

如果为小问题找到的最优解,能通过增加一点步骤,解决一个大一点的问题,并依然是最优解。

则采用贪心法,从0开始,逐步蚕食掉大问题。

3.动态规划

如果用分治法拆出的小问题中常见到相同问题,重复计算它们,成本太高。

则采用备忘法,计算完每个小问题的结果后,记录之,下次见到同一小问题,不再重复计算。

 

一、数学基础

《算法导论》在附录中给出了4项必备的数学基础。

我看了之后,很羡慕考研的同学,他们这几门课都很扎实。

这4门数学除了是考研数学科目、算法的基础外,其实更是观察世界、指导生活(不仅仅是生产!)的工具,我决定要以看公开课的方式,逐步重新学之。

1.微积分

2.离散数学

3.概率论

4.线性代数

 

二、线性表

1.按实现分类

顺序表:随机访问方便,插入删除成本高,因为一侧的元素要「哒哒哒」依次移动一格。

链表:随机访问麻烦,因为要从头「一二三」数过去,插入删除方便,将特定两三个节点的指针「咔吧」重新接一下就好了。

2.按作用分类

栈:后进先出,直观理解就是坐电梯。用处主要在处理大问题时,细化为小问题,小问题解决完再继续处理大问题的时候。计算机的函数调用的核心数据结构。如果不幸小问题没完没了,如无限递归,则stackoverflow。

队列:先进先出,讲「先来后到」的数据结构。典型使用就是「任务队列」,先到的先处理。如果允许「插队」,就是「优先级队列」了,让领导先走!

 

三、排序

假设有一个初始队列4132,目标是从小到大排序成1234。

1.冒泡排序

最简单也最慢的算法,慢到不少书都不讲了。

思想是让最后一个元素尽力向上爬,遇见比它大的就压过之(交换次序),如果遇到比它小的就停下,由小的继续往上爬。爬到第一个元素时,就保证了第一个元素是全部元素中最小的一个。

不再考虑第一个元素,重复这一过程。4132,1/423,12/43,123/4。

2.选择排序

每次都从队列中选出一个最小的元素,放到「已排序队列」里,直到选完。

/4132,1/432,12/43,12/34。

3.插入排序

每次都从「未排序队列」中选第一个元素,插到「已排序队列」的适当位置,直到插完。

我玩扑克时理牌就用这法。

4/132,14/32,134/2,1234

4.希尔排序

先把「相距较大间距」的元素们排序一遍,再适度减小间距再排一遍,最后一次相距零间距排。

4132,先间隔较大间距(这个简陋例子,姑且间隔1),4与3排序,1与2排序,得3142,再间隔较小间距(本例中直接到0了)排序。

5.快速排序

最被喜欢的排序,既容易理解,又快。

选一个数字为轴,比它小的放左边,比它大的放右边,然后对其两边各进行这一变化即可。

4132,第一步选4,第二步选1,都是把全部剩余元素放到同侧,不划算,所以随机选择轴元素很关键。

假设第一步选了3,12放左侧,4放右侧,右侧完结,左侧继续,假设选2为轴,1放左侧,右侧没有,即得结果1234。

6.归并排序

所谓归并,比如一班和二班已经各排成了从矮到高的有序队列,想归并成一队,怎么办?比较一班和二班的排头,更矮的选出来站到「结果队列」里,该班的新排头再跟对方排头比,以此类推。

归并成一个新队列后,再跟别的队列归并,直到统统归并为一队。

14/23 -> 1|4/23 -> 12|4/3 -> 123|4 -> 1234

7.堆排序

所谓堆,就是一棵每个父节点数值都大于其一切子孙节点数值的完全二叉树,如果看不懂,先跳到下面看树那节。

为方便说(放图太麻烦了,我相信纯文字能说清),这次咱们从大到小排序,道理当然是一样的。

分两步,一是从无序队列构造树,二是从树输出有效队列,结合起来,就是从无序队列,得到了有序队列。

第一步,拿一个新节点,放到原树的最后一个位置,然后使之尽力向上冒泡,直到冒不动为止,再拿下一个新节点。如处理4132:

4 -> 4左下1 -> 4左下1右下3 -> 4左下1右下3,1左下2 -(2冒泡)-> 4左下2右下3,2左下1

第二步,取出根节点放到结果队列,把最后一个节点僭越到根位置,然后考察其两个叶子节点,如果有更有实力的,则向最有实力的退位让贤,交换位置,到新岗位后继续考察下属能力,直到降到自己胜任的位置。

4左下2右下3,2左下1 -(取出4,1上位)-> 1左下2右下3 -(3篡位)-> 3左下2右下1 -(取出3,1上位)-> 1左下2 -(2篡位)-> 2左下1 -(取出2)-> 1孤家寡人 -(取出1)-> 结果4321

 

四、树

若干节点,及若干连接节点的无向边,构成的图,如果从每个节点出发,都能到达任意一个节点(强连通),同时图中不存在环,即称为树。

数据结构中说的树,在此基础上再严格点,分为若干层。如某团长手下有若干连长,每个连长手下有若干班长,画组织结构图,把直接领导和直接下属连接起来。直接领导称为父节点,如团长是连长的父节点,连长是其属下每个班长的父节点;直接下属称为子节点;最高长官称为根节点,即没有父节点的节点;没有子节点的节点称为叶子节点,比如《士兵突击》里钢七连只剩老七(连长)和三多(班长)的时候,三多是叶子节点,如果这时三多被老A挖走(实际剧情是老七先走,不赘),则老七堂堂连长,将不幸成为叶子节点。

1.二叉树

如果树的每个父节点最多只有两个子节点,该树即称为二叉树。

最典型用途是二叉查找,即如果每个根节点数值都比其左子树(此概念望文生义,不赘)任意节点数值更大,比其右子树的任意节点数值更小,该树即称为二叉排序树。在想寻找某个数值时,可以先将该数值与根节点比,如果比根节点大,则去与其右子树根节点比,如果比根节点小,则去与其左子树根节点比,直到找到或比到叶子节点为止。

好像「猜数字」游戏,一本好书价值1元到256元之内,假设你蠢到看不出那书不可能1元,又聪明到知道采用二叉查找,则该先猜128元,根据主持人说「高了」「低了」再决定猜64还是192元,假如64还是「高了」,则该继续猜32,以此类推。

2.红黑树

强烈推荐看《算法》中红黑树的章节,从2-3树开始讲,讲到红黑树,学习曲线非常平滑。

二叉树和红黑树都有着清晰的用于保持树平衡的逻辑,限于篇幅不多讲。平衡的目的是保持最差情况下的查找程度为logN(以2为底,总节点数的对数)。

3.散列表

这个不是树……但在逻辑上放在这里最好,因为都是用于「查找」的数据结构。

编程中最基本的两种数据结构,list和map,list就是上文说的线性表,核心是有顺序,map就是这里说的散列表(hashmap)或树(treemap),核心是键值对。set呢,多以map做底层结构。

树上面说了,这里说散列表。

散列表又叫字典,从这字面可知,主要用途是查找,通过键(key)查找值(value),首先,要把键算成一个数字,这算法(散列函数)就是java里类们都要实现的hashcode方法。

然后,有两种可选的实现方式,一是链接法,首先有个主list装着键们,比如123,然后1对应一个list,2对应一个list,3对应一个list,我把键算出是1之后,就到1对应的list元素里去找元素。显然,1对应的list长度越短,查找时间越短,那似乎主list的键们越多越好,比如1到30,那每个子list的长度将变为原长度的十分之一,但主list的键们也不能太多,比如1到30000,那大部分键对应的其实是空,里面一个元素都没有,就浪费空间了,所以要权衡。

另一种实现方式是散列法,不存在次list,把键算成数字后,直接往主list对应的位置存,如果该位置已经被别的元素占了(碰撞)怎么办?则用某种算法,算出一个新数,再尝试往新位置放(再散列),以此类推。显然,这种方法,主list的长度也很关键,如果太短,则碰撞太多,插入、查找都麻烦,如果太长,又浪费地方。

对两种方法,散列函数都非常重要,如果所有元素的散列函数都计算出同一个值,散列表就毫无意义了。

 

五、图

终于到图了!这是我最喜欢的部分,好玩,而且熟悉,因为我认识一个同学,数据结构年年挂,直到大四,所以我每年都陪他复习备考一次,老师考卷中的高分的题目,就是考图的几个算法,迪杰斯特拉,普里姆,克鲁斯卡尔……好怀念那段日子。

什么是图?一堆节点,及若干边,就构成了图,根据线路是否有方向性,分为有向图、无向图,根据图中是否有环,分为有环图、无环图。

如果任意两个节点都有线路连接,则称为强连通图,这里主要聊的都是这种。

1.深度优先、广度优先遍历

A连B,B连C,B连D,C连E

想把图里所有节点都研究一遍,怎么办?

从一个节点开始,走向下一个节点,然后再走向下一个节点的下一个节点,直到「眼前无路想回头」,就是「深度优先遍历」。在例子里,从A到B,从B到C,从C到E,E回头到C,C回头到B,从B到D,完成遍历。

「广度优先遍历」则是,从一个节点开始,先扇面状把能到的节点都扫一遍(广嘛),然后再「移步」到子节点们。在例子里,从A到B,从B到C,从B到D,从C到E,完成遍历。

2.最小生成树

如果树的每条边都有个权值,要求选出总权值最小的一些边,让所有节点都能互相连通,怎么办?

这就是「最小生成树」问题,显然,选出的结果肯定是一棵树,树的两个条件,连通和无环,连通不必讲,为什么无环?如果有环,去掉任意一条边,节点们依然相互连通,权值变小了,由此反证,必然无环。

解此问题,两种方法,一是普里姆算法,二是克鲁斯卡尔算法,好专业,终于有点算法的感觉了。

其实都很简单,先说普里姆,将图划为「已解决」和「未解决」两个部分,一开始「已解决」为空,「未解决」是全集,首先,任选一个点放到「已解决」,然后考察所有从「已解决」连向「未解决」的边,哪条最短,就把该边连向的「未解决」节点纳入「已解决」集合,如此反复,直到全部节点都「已解决」,结果就是最小生成树。

再说克鲁斯卡尔,一开始,把每个节点视为一个「分量」,寻找全部「连接两个不同分量的边」中最短的一条,将其连接的两个分量合并为一个分量,并重复这一行为,直到全部节点都属于同一分量,结果就是最小生成树。

3.单源最短路径

最小生成树研究的是无向图,最短路径则研究有向图。

顾名思义,最短路径是要求给出从某地到另外某地的最便捷走法,这有两个算法,一是迪杰斯特拉算法,二是贝尔曼福特算法。

先说迪杰斯特拉,这是类似普里姆的「贪婪算法」,从一个极小的「已解决」开始,逐步蚕食,直到将「未解决」吃掉。差别在这回每个节点上都有个数字,代表其到起点的距离,每次都选全部「从已解决到未解决的边」指向的「未解决」节点中,数字最小的一个。比如起点是家,家距离学校500米,家距离市场600米,学校距离公园200米,根据算法,把学校标注500,市场标注600,500小于600,把学校纳入「已解决」,学校进入「已解决」之后,公园也变成了从「已解决」可以到达的「未解决」的节点,用学校的500加200,公园标注为700,与市场的600米相比,600较小,把市场纳入「已解决」。注意,这个步骤,如果是普里姆算法,纳入的是公园而非市场,因为普里姆不存在起点,都连上就ok,只考虑哪条边最短,但迪杰斯特拉有起点,要比较的是「从起点出发直到这里的距离」。

再说贝尔曼福特,这算法是把每个节点赋予一个表示「距离起点有多远」的数值,除了起点外,其他起点一开始都是无穷大,然后依次考察每条边,如果这条边能让指向的节点的数值变小,就将该节点数值变小(收缩),把所有边都考察一遍之后,如果这一遍中执行了「收缩操作」,则再把所有边都考察一遍,直到某一遍完全没收缩为止。上面的例子,比如考察次序是200-500-600,则第一遍200啥用没有,500将学校的+∞变为500,600将市场的+∞变为600,这遍进行了收缩,再来一遍,这回200有用了,将公园的+∞变为700,500和600都没有,这遍也收缩了,再来一遍,200/500/600都没用,完结。

 

六、字符串

字符串本质是字符数组。说到算法,最常说的就是字符串查找的KMP算法。

比如想从「子龙子龙世无双」里寻找「子龙子翼」,「子」等于「子」,「龙」等于「龙」,「子」等于「子」,「龙」不等于「翼」,糟糕!这时源文本的「已搜索序列」的「后缀们」有「子龙子龙」「龙子龙」「子龙」「龙」四个,而目标文本的「前缀们」有「子龙子翼」「子龙子」「子龙」「子」四个,考察两个「们」,发现有个相同元素,即「子龙」,长度为2(如果有多个相同元素,则取最长的),意味着源文本的「已搜索序列」中最后两个字与目标文本的前两个字相同,下次用源文本的下一个字「世」与目标文本的第三个字「子」相比即可。如果是朴素算法,则要用「子龙子龙世无双」的第一个「龙」字与「子龙子翼」的第一个「子」字相比,KMP算法比朴素算法快多了!

 

七、写在后面

算法的水太深,我仅仅入了个门,回头看看,上面所写,全是大学《数据结构》的内容,长叹一声。

也有更深入学习的意愿,但在这之前要巩固数学基础,我在看网易公开课上的《线性代数》和《微积分》的公开课。

好在,这些「入门知识」,平日工作倒也够用,而数学、计算机基础的巩固和学习,是一辈子的事,不用太急。

不要哀叹过去的荒芜,唯一的方法是立足于现在的状态,选取最优的进步路线,勤勉地躬行之。

学过一点点经济学基础的人,不会为「沉没成本」沮丧。

 

数学太美,逻辑太美,算法太美。

我却近来才发现。读书的时候全没省得。

不省得也没关系,老老实实听话就好,现在想想,是「独立思考」得过于早了。

这是我的人生历程,没什么可后悔,写这只是想规谏还在念书的朋友。

别急着自行其是,以后的人生里,有的是机会让你自行决策,还在念书的时候,请听话。

听老师的话,好好学习,天天向上。

关键词:
渝ICP备16002246号 Copyright © 2017. Singee77.com