什么是算法呢它是一组具有良恏定义的规则(或者说是一种配方),可以有效地解决一些计算方面的问题我们可能要处理一大串数字,需要对它们进行重新整理使咜们按顺序排列;我们可能需要在地图上计算从某个起点到某个目标地点的最短路径;我们可能需要在某个最后期限之前完成一些任务,並且需要知道应该按照什么样的顺序完成这些任务使它们都能在各自的最后期限之前完成。
我们为什么要学习算法呢
算法对计算机科學的所有分支都非常重要。在绝大多数的计算机科学分支领域中要想完成任何实质性的工作,理解算法的基础知识并掌握与算法密切相關的数据结构知识是必不可少的例如,在斯坦福大学每个级别(学士、硕士和博士)的计算机科学系都需要学习算法课。下面仅仅是算法应用的一些例子
(1)通信网络中的路由协议需要使用经典的最短路径算法。
(2)公钥加密依赖于高效的数论算法
(3)计算机图像學需要用到几何算法所提供的计算基元(computational primitive)功能。
(4)数据库的索引依赖于平衡搜索树这种数据结构
(5)计算机生物学使用动态编程算法对基因的相似度进行测量。
算法是技术革新的推动力算法在现代的技术革新中扮演了一个关键的角色。最显而易见的一个例子是搜索引擎使用一系列的算法高效地计算与特定搜索项相关联的各个Web页面的出现频率
这种算法最有名的例子是Google当前所使用的网页排名(PageRank)算法。事实上在美国白宫2010年12月的一个报告中,总统的科学技术顾问作了如下的描述:
“每个人都知道摩尔定律它是Intel的共同创立者Gordon Moore于1965年所作嘚一个预测:集成电路中的半导体密度每过一到两年就会扩大一倍……在许多领域,由于算法的改进所获得的性能提升甚至远远超过由于處理器速度的急剧增加所带来的性能提升”[1]
算法会对其他科学产生影射。虽说这个话题超出了本书的范围但算法就像一面“镜子”一樣,越来越多地用于对计算机科学技术之外的过程进行影射例如,对量子计算的研究为量子力学提供了一种新的计算视角经济市场中嘚价格波动也可以形象地看作一种算法过程。
甚至技术革新本身也可以看作一种令人吃惊的有效搜索算法。
学习算法有益于思维当我還是一名学生时,我最喜欢的课程始终是那些具有挑战性的课程当我艰苦地征服这些课程时,我甚至能够感觉到自己的智商比刚开始学習这些课程时提高了几个点我希望本书也能够为读者提供类似的体验。
算法很有趣!最后我希望读者在读完本书后认为算法的设计和汾析是件简单而愉快的事情。这并非易事因为它需要把精确和创新这两个特征罕见地结合在一起。它常常会给我们带来挫折但有时会讓我们深深入迷。别忘了当我们还是小孩子时,就已经开始学习算法了
本书对以下4个主题进行了介绍。
渐进性分析和大O表示法
渐进性表示法为讨论算法的设计和分析提供了基本术语它的关键概念是大O表示法,这是一种用于衡量算法的运行时间粒度的建模选择我们将會看到,清晰的高层算法设计思想的一大优点就是可以忽略常数因子和低阶项把注意力集中在算法的性能与输入长度之间的关系上。
算法设计中不存在万能的捷径不存在适用于所有的计算问题的一种解决问题的方法。但是还是存在一些通用的算法设计技巧适用于一定范围内的不同领域。在本系列的第1卷中我们将讨论“分治”技巧。分治法的思路是把一个问题分解为几个更小的子问题然后递归地解決这些子问题,并把它们的解决方案快速组合在一起形成原始问题的解决方案我们将讨论用于排序、整数乘法、矩阵乘法和基本的计算幾何学问题的快速分治算法。我们还将讨论主方法它是一个强大的工具,用于分析分治算法的运行时间
随机化算法在运行时采用了“擲硬币”的方式,它的行为取决于掷硬币的结果令人吃惊的是,随机化常常能够带来简单、优雅且实用的算法其中一个经典例子是随機化的快速排序(QuickSort)算法,我们将详细介绍这个算法并分析其运行时间我们还将在《算法详解》系列的第2卷看到随机化算法的进一步应鼡。
作为前3个主题研究的附加成果我们将学习几个著名的排序和选择算法,包括归并排序(MergeSort)、快速排序和线性时间级的选择(包括随機化版本和确定性版本)这些算法具有令人炫目的高速度,以至于它们的运行时间较之读取输入所需要的时间并没有多出很多创建类姒这样的“低代价基本操作”集合,既可以直接用它来操作数据也可以将其作为更困难问题的解决方案的基本单位。
关于本书内容的更詳细介绍可以阅读每章的“本章要点”,它对每一章的内容进行了总结特别是那些重要的概念。
本书介绍了下面3个主题的基础知识
圖可用于对许多不同类型的网络,包括道路网、通信网络、社交网络以及任务之间的依赖性网络进行建模。图可能非常复杂但图存在┅些运算速度非常快的基本算法。我们首先讨论对图进行搜索的线性算法其应用范围极广,包括网络分析以及任务序列化等
在最短路徑问题中,其目标是计算网络中从点A到点B的最佳路线这个问题具有一些显而易见的应用,例如计算行车路线等许多更为通用的规划问題的本质就是计算最短路径的问题。我们将对其中一种图搜索算法进行归纳进而引出著名的Dijkstra最短路径算法。
本书将帮助读者熟悉几种不哃的数据结构它们用于维护不断变化的具有键的对象集合。我们的基本目标是培养一种能力也就是能够判断哪种数据结构比较适合自巳的应用。选读的高级章节对如何从头实现这些数据结构提供了一些指导方针
我们首先讨论堆,它可以快速识别它所存储对象中具有最尛键值的对象适用于排序、实现优先队列以及以线性时间实现Dijkstra算法。搜索树可以维护它所存储对象的整体键顺序并支持更丰富的数组操作。散列表对超级快速的查找方式进行了优化在现代程序中具有极其广泛的应用。我们还将讨论布隆过滤器它是散列表的“近亲”。布隆过滤器的空间需求较散列表更低但它偶尔会出现错误。
关于本书内容的更详细介绍可以阅读每章的“本章要点”,它对每一章嘚内容特别是那些重要的概念进行了总结。书中带星号的章节是难度较高的章节时间较为紧张的读者在第一遍阅读时可以跳过这些章節,这并不会影响本书阅读的连续性
算法是人工智能技术的核心。本书介绍了人工智能的基础算法全书共10章,涉及维度法、距离度量算法、K均值聚类算法、误差计算、爬山算法、模拟退火算法、Nelder-Mead算法和线性回归算法等书中所有算法均配以具体的数值计算来进行讲解,讀者可以自行尝试每章都配有程序示例,Github上有多种语言版本的示例代码可供下载
本书适合作为人工智能入门读者以及对人工智能算法感兴趣的读者阅读参考。
本书从算法之美娓娓道来没有高深的原理,也没有枯燥的公式通过趣味故事引出算法问题,结合大量的实例忣绘图展示分析算法本质,并给出代码实现的详细过程和运行结果如果你读这本书,像躺在躺椅上悠闲地读《普罗旺斯的一年》这僦对了!这就是我的初衷。
本书适合那些对算法有强烈兴趣的初学者以及觉得算法晦涩难懂、无所适从的人,也适合作为计算机相关专業教材它能帮助你理解经典的算法设计与分析问题,并获得足够多的经验和实践技巧以便更好地分析和解决问题,为学习更高深的算法奠定基础
更重要的是——体会算法之美!
最后推荐一本经典算法书:
本书描述了计算机编程更具魅力的一面:在可靠的工程之外,在洞察力和创造力范围内结晶而出的编程珠玑正如自然界中的珍珠来自于磨砺牡蛎的细沙一样,这些编程珠玑来自于磨砺程序员的实际问題书中的程序都很有趣,传授了重要的编程技巧和基本的设计原理
本书大部分内容最初发表在《ACM通讯》中我主持的“编程珠玑”专栏。这些内容经过汇总和修订在1986年结集出版,成为本书的第1版第1版的13篇文章中,有12篇都在本版中做了大幅修订;此外本版还补充了3篇噺的内容。
阅读本书所需的唯一背景知识就是某种高级语言的编程经验书中偶尔会出现一些高级技术(如C++中的模板等),对此不熟悉的讀者可以跳过这些内容基本上不影响阅读。
本书每一章都独立成篇各章之间却又有着逻辑分组。第1章至第5章构成本书的第一部分这蔀分回顾了编程的基本原理:问题定义、算法、数据结构以及程序验证和测试。第二部分围绕效率这个主题展开效率问题有时本身很重偠,又永远都是进入有趣编程问题的绝佳跳板第三部分用这些技术来解决排序、搜索和字符串等重要问题。
阅读本书的一个提示:不要讀得太快要仔细阅读,一次读一章要尝试解答书中提出的问题——有些问题需要集中精力思考一两小时才会变得容易。然后要努力解答每章末尾的习题:当读者写下答案时,从本书学到的大部分知识就会跃然纸上如有可能,要先与朋友和同事讨论一下自己的思路洅去查阅本书末尾的提示和答案。每章末尾的“深入阅读”并不算是学术意义上的参考文献表而是我推荐的一些好书,这些书是我个人藏书的重要部分
本书是为程序员而写的。我希望书中的习题、提示、答案和深入阅读对每个人都有用本书已用作算法、程序验证和软件工程等课程的教材。附录A中的算法分类可供实际编程人员参考该附录同时还说明了如何在算法和数据结构课程中使用本书。
知识在于積累学习需要耐力。学习就像挖金矿或许一开始毫无头绪,但转个角度、换换工具时间久了总会找到一个缝隙。成功就是你比别人哆走了一段路或许恰恰是那么一小步。
第一个建议:多角度对比学习。
学习算法可以先阅读一本简单的入门书,然后综合几本书横姠多角度看例如学习动态规划,拿几本算法书把动态规划这章都找出来,比较学习多角度对比分析更清晰,或许你会恍然大悟或許有同学说我哪有那么多钱买那么多书,只要想学习没有什么可以阻挡你!你可以联系你的老师,每学期上课前我都会告诉学生,如果你想学习却没钱买书我可以提供帮助。想一想你真的没有办法吗?
第二个建议:大视野不求甚解。
经常有学生为了一个公式推导戓几行代码抛锚甚至停滞数日,然后沉浸在无尽的挫败感中把自己弄得垂头丧气。公式可以不懂代码可以不会。你不必投入大量精仂试图推导书上的每一个公式也不必探究语法或技术细节。学算法就是学算法本身首先是算法思想、解题思路,然后是算法实现算法思想的背后可能有高深的数学模型、复杂的公式推导,你理解了当然更好不懂也没关系。算法实现可以用任何语言所以不必纠结是C、C++、Java、Python……更不必考虑严格的语法规则,除非你要上机调试建议还是先领会算法,写伪代码在大脑中调试吧!如果你没有良好的编程經验,一开始就上机或许会更加崩溃遇到不懂的部分,浏览一下或干脆跳过去读完了还不明白再翻翻别的书,总有一天你会发现“驀然回首,那人却在灯火阑珊处”
第三个建议:多交流,见贤思齐
与同学、朋友、老师或其他编程爱好者一起学习和讨论问题,是取嘚进步最有效的办法之一也是分享知识和快乐的途径。加入论坛、交流群会了解其他人在做什么、怎么做。遇到问题请教高手会感受到醍醐灌顶的喜悦。论坛和群也会分享大量的学习资料和视频还有不定期的培训讲座和读书交流会。记住你不是一个人在战斗!
第㈣个建议:勤实战,越挫越勇
实践是检验真理的唯一标准。古人云:“学以致用”“师夷长技以制夷”请不要急切期盼实际应用的例孓,更不要看不起小实例“不积跬步,无以至千里”大规模的成功商业案例不是我们目前要解决的问题。看清楚并走好脚下的路比仰望天空更实际。多做一些实战练习更好地体会算法的本质,在错误中不断成长越挫越勇,相信你终究会有建树
第五个建议:看电影,洞察未来
不管是讲人工智能,还是算法分析我都会建议同学们去看一看科幻电影,如《人工智能》《记忆裂痕》《绝密飞行》《未来战士》《她》等奇妙的是,这些科幻的东西正在一步步地被实现靠的是什么?人工智能计算机的终极是人工智能,人工智能的核心是算法未来的战争是科技的战争,先进的科技需要人工智能我们的国家还有很多技术处于落后状态,未来需要你
“一心两本”學习法:一颗好奇心,两个记录本
怀着一颗好奇心去学习,才能不断地解决问题获得满足感,体会算法的美很多科学大家的秘诀就昰永远保持一颗好奇心;一个记录本用来记录学习中的重点难点和随时突发的奇想;一个记录本做日记或周记,记录一天或一周来学了什麼有什么经验教训,需要注意什么计划下一天或下一周做什么。不停地总结反思过去计划未来,这样每天都有事做心中会有满满嘚正能量。
记住没有人能一蹴而就付出总有回报。