PDF《数据结构与算法（DSA）》

数据结构与算法(DSA) 序 自诩文艺青年,却一晃而立.

自小蒙应试教育指导,对很多知识都是处于 知之为不知的状态,甚是惭愧.因安身立命之由,踏入程序不归路,路上荆棘 遍布.同时也有很多披襟斩棘之士,是故,吾辈可拾前人牙慧,填补空缺,砥 砺前行.本教程便是翻译自国外大神文章,如若有版权问题,请及时联系我 本教程对理解基础数据结构和算法很有帮助.我看完以后,就迫不及待的 想把它分享给跟我一样:编程基础不是很扎实的 假程序员 .由于水平有限, 很怕对原文理解有差错而误人子弟 , 所以我建议有时间和条件的可以多去看看 原文,如若阅读之后发现有不对的地方,欢迎发邮件告知,不胜感激 本译作采用知识共享署名-非商业性使用-禁止演绎 3.0 本地化版本许可协 议进行许可 译文原址:《 Data Structures and Algorithms (DSA)》 译者

邮箱: [email protected] 凌泽 2018.07.11

第一章:时间复杂度和大 O 表示法 作为一名开发人员 , 你其实有能力改变世界 ! 你可以编写程序来支持新的 技术,可以编写软件用来辅助诊断疾病更早期的形态.你也可以编写程序用来节 约人们的时间去做其他更有意思的事情.只要你用心去做,它都有可能影响你 周围的人 然而要做到上面那些,前提就是我们编写的软件要运行的稳定、快速以及可 扩展性强. 这个系列的译文就是学习如何度量你的代码性能 我们将分析代码的算法以及使用时间复杂度(time complexity)和大 O 表 示法(big O notation)来度量你的代码性能.首先 , 让我们看一个真实的故事来 了解为什么代码性能很重要 1. 算法的力量 1.1 图灵大破英格玛 第二次世界大战期间,德国使用 AM 信号与欧洲各地的部队进行通讯,任何 有AM 收音机和懂一些莫尔斯电码的人都可以拦截这个信息.然而,这些信息 是加了密的.所有反法西斯国家都试图用纸和笔去破解这些加密信息,运气好的 时候,能够破解一部分信息.不幸的是 , 纳粹分子每天都会更换加密的方式 一个叫图灵的数学天才加入了英国军队 , 试图破解德国的英格玛 .他知道 如果用笔和纸去计算的话 , 是永远都不可能成功的.经过几个月的努力,他的团 队制造了一台机器用来解密信息, 但是它破解的速度太慢 , 需要超过一天的时间 因为纳粹分子每天都更换加密方式,所以这个机器虽然破解了信息,但是信息 已经过期作废了 正当大家很沮丧,一筹莫展甚至想要放弃,关掉这台机器的时候,图灵他 们发现,解密后的信息都以 希特勒万岁! 这句话结束,于是他们就跟据这个 突破口改变机器的算法,大大提高了破解信息的速度,因此能料敌先机,拯救 百万人生命;

有兴趣的可以拓展阅读:图灵是如何破译英格玛 同一台机器,因为失败的算法导致将关闭,又因为改善了算法从而拯救数百万人性命;

同样,你也可以改善你的代码性能让你的电脑能做更多的事情,这就是这篇译文要学习的 东西 1.2 网页排名算法 另一个广为流传的算法是:网页排名(PageRank)算法.它是谢尔盖・布林 和拉里・佩奇在

1998 年发明的算法.它被谷歌搜索引擎用来搜索数万亿的网页. 谷歌并不是唯一的搜索引擎,但是它搜索返回的结果更快更精准,所以谷歌占 领全球绝大部分搜索市场(中国除外) , 这就是算法的力量 2. 为什么你要学习编写高效的算法呢? 当然有很多原因,我随便列举一些: ? 提交面试机会,找到更心仪的工作 ? 你会成为一位更优秀的软件开发者 ? 减少调试、优化以及重写代码的时间 ? 在相同的硬件下,你的软件有更优秀的表现 ? 可以用来拯救百万人生命(比如:更早的发现疾病,用机器代替人在危险的 环境下工作等) ? 超越你的竞争对手 言归正传,开始我们的学习吧! 3. 什么是算法? 算法其实就是你完成某些任务的步骤.当你做菜的时候,你会按照菜谱 (菜谱就是算法)去制作一道菜;