送书 | 你一定能看懂的算法基础书(代码示例基于Python)-程序员宅基地



本文引自图灵教育《算法图解》


你一定能看懂的算法基础书;代码示例基于Python;400多个示意图,生动介绍算法执行过程;展示不同算法在性能方面的优缺点;教会你用常见算法解决每天面临的实际编程问题。


参与方式:喜欢这本书,请在评论区留言,和大家分享你在学习算法过程中的一些经验和心得,根据评论质量和评论点赞数,前五名同学可获得本书。活动截止时间为11月27日(下周一22点

算法简介

 

本章内容


  • 为阅读后续内容打下基础。

  • 编写第一种查找算法——二分查找。

  • 学习如何谈论算法的运行时间——大O表示法。

  • 了解一种常用的算法设计方法——递归。

 

1.1 引言


算法是一组完成任务的指令。任何代码片段都可视为算法,但本书只介绍比较有趣的部分。本书介绍的算法要么速度快,要么能解决有趣的问题,要么兼而有之。下面是书中一些重要内容。


  • 第1章讨论二分查找,并演示算法如何能够提高代码的速度。在一个示例中,算法将需要执行的步骤从40亿个减少到了32个!

  • GPS设备使用图算法来计算前往目的地的最短路径,这将在第6、7和8章介绍。

  • 你可使用动态规划来编写下国际跳棋的AI算法,这将在第9章讨论。


对于每种算法,本书都将首先进行描述并提供示例,再使用大O表示法讨论其运行时间,最后探索它可以解决的其他问题。


1.1.1 性能方面


好消息是,本书介绍的每种算法都很可能有使用你喜欢的语言编写的实现,因此你无需自己动手编写每种算法的代码!但如果你不明白其优缺点,这些实现将毫无用处。在本书中,你将学习比较不同算法的优缺点:该使用合并排序算法还是快速排序算法,或者该使用数组还是链表。仅仅改用不同的数据结构就可能让结果大不相同。


1.1.2 问题解决技巧


你将学习至今都没有掌握的问题解决技巧,例如:


  • 如果你喜欢开发电子游戏,可使用图算法编写跟踪用户的AI系统;

  • 你将学习使用K最近邻算法编写推荐系统;

  • 有些问题在有限的时间内是不可解的!书中讨论NP完全问题的部分将告诉你,如何识别这样的问题以及如何设计找到近似答案的算法。


总而言之,读完本书后,你将熟悉一些使用最为广泛的算法。利用这些新学到的知识,你可学习更具体的AI算法、数据库算法等,还可在工作中迎接更严峻的挑战。


需要具备的知识

要阅读本书,需要具备基本的代数知识。具体地说,给定函数f(x) = x × 2,f(5)的值是多少呢?如果你的答案为10,那就够了。


另外,如果你熟悉一门编程语言,本章(以及本书)将更容易理解。本书的示例都是使用Python编写的。如果你不懂任何编程语言但想学习一门,请选择Python,它非常适合初学者;如果你熟悉其他语言,如Ruby,对阅读本书也大有帮助。


1.2 二分查找


假设要在电话簿中找一个名字以K打头的人,(现在谁还用电话簿!)可以从头开始翻页,直到进入以K打头的部分。但你很可能不这样做,而是从中间开始,因为你知道以K打头的名字在电话簿中间。



又假设要在字典中找一个以O打头的单词,你也将从中间附近开始。


现在假设你登录Facebook。当你这样做时,Facebook必须核实你是否有其网站的账户,因此必须在其数据库中查找你的用户名。如果你的用户名为karlmageddon,Facebook可从以A打头的部分开始查找,但更合乎逻辑的做法是从中间开始查找。


这是一个查找问题,在前述所有情况下,都可使用同一种算法来解决问题,这种算法就是二分查找。

 

二分查找是一种算法,其输入是一个有序的元素列表(必须有序的原因稍后解释)。如果要查找的元素包含在列表中,二分查找返回其位置;否则返回null。


下图是一个例子。



 下面的示例说明了二分查找的工作原理。我随便想一个1~100的数字。


 

你的目标是以最少的次数猜到这个数字。你每次猜测后,我会说小了、大了或对了。


假设你从1开始依次往上猜,猜测过程会是这样。


 


这是简单查找,更准确的说法是傻找。每次猜测都只能排除一个数字。如果我想的数字是99,你得猜99次才能猜到!


1.2.1 更佳的查找方式


下面是一种更佳的猜法。从50开始。



小了,但排除了一半的数字!至此,你知道1~50都小了。接下来,你猜75。



大了,那余下的数字又排除了一半!使用二分查找时,你猜测的是中间的数字,从而每次都将余下的数字排除一半。接下来,你猜63(50和75中间的数字)。



这就是二分查找,你学习了第一种算法!每次猜测排除的数字个数如下。


不管我心里想的是哪个数字,你在7次之内都能猜到,因为每次猜测都将排除很多数字!


假设你要在字典中查找一个单词,而该字典包含240 000个单词,你认为每种查找最多需要多少步?


如果要查找的单词位于字典末尾,使用简单查找将需要240 000步。使用二分查找时,每次排除一半单词,直到最后只剩下一个单词。



因此,使用二分查找只需18步——少多了!一般而言,对于包含n个元素的列表,用二分查找最多需要log2n步,而简单查找最多需要n步。


对数


你可能不记得什么是对数了,但很可能记得什么是幂。log10100相当于问“将多少个10相乘的结果为100”。答案是两个:10 × 10 = 100。因此,log10100 = 2。对数运算是幂运算的逆运算。


对数是幂运算的逆运算

 

本书使用大O表示法(稍后介绍)讨论运行时间时,log指的都是log2。使用简单查找法查找元素时,在最糟情况下需要查看每个元素。因此,如果列表包含8个数字,你最多需要检查8个数字。而使用二分查找时,最多需要检查log n个元素。如果列表包含8个元素,你最多需要检查3个元素,因为log 8 = 3(23 = 8)。如果列表包含1024个元素,你最多需要检查10个元素,因为log 1024 = 10(210 =1024)。


本书经常会谈到log时间,因此你必须明白对数的概念。如果你不明白,可汗学院(khanacademy.org)有一个不错的视频,把这个概念讲得很清楚。

 

说明

仅当列表是有序的时候,二分查找才管用。例如,电话簿中的名字是按字母顺序排列的,因此可以使用二分查找来查找名字。如果名字不是按顺序排列的,结果将如何呢?


下面来看看如何编写执行二分查找的Python代码。这里的代码示例使用了数组。如果你不熟悉数组,也不用担心,下一章就会介绍。你只需知道,可将一系列元素存储在一系列相邻的桶(bucket),即数组中。这些桶从0开始编号:第一个桶的位置为#0,第二个桶为#1,第三个桶为#2,以此类推。


函数binary_search接受一个有序数组和一个元素。如果指定的元素包含在数组中,这个函数将返回其位置。你将跟踪要在其中查找的数组部分——开始时为整个数组。



你每次都检查中间的元素。



如果猜的数字小了,就相应地修改low



如果猜的数字大了,就修改high。完整的代码如下。



练习

1.1 假设有一个包含128个名字的有序列表,你要使用二分查找在其中查找一个名字,请问最多需要几步才能找到?

1.2 上面列表的长度翻倍后,最多需要几步?


1.2.2 运行时间

每次介绍算法时,我都将讨论其运行时间。一般而言,应选择效率最高的算法,以最大限度地减少运行时间或占用空间。


回到前面的二分查找。使用它可节省多少时间呢?简单查找逐个地检查数字,如果列表包含100个数字,最多需要猜100次。如果列表包含40亿个数字,最多需要猜40亿次。换言之,最多需要猜测的次数与列表长度相同,这被称为线性时间(linear time)。


二分查找则不同。如果列表包含100个元素,最多要猜7次;如果列表包含40亿个数字,最多需猜32次。厉害吧?二分查找的运行时间为对数时间(或log时间)。下表总结了我们发现的情况。

 


1.3 大O表示法


大O表示法是一种特殊的表示法,指出了算法的速度有多快。谁在乎呢?实际上,你经常要使用别人编写的算法,在这种情况下,知道这些算法的速度大有裨益。本节将介绍大O表示法是什么,并使用它列出一些最常见的算法运行时间。


1.3.1 算法的运行时间以不同的速度增加


Bob要为NASA编写一个查找算法,这个算法在火箭即将登陆月球前开始执行,帮助计算着陆地点。


这个示例表明,两种算法的运行时间呈现不同的增速。Bob需要做出决定,是使用简单查找还是二分查找。使用的算法必须快速而准确。一方面,二分查找的速度更快。Bob必须在10秒钟内找出着陆地点,否则火箭将偏离方向。另一方面,简单查找算法编写起来更容易,因此出现bug的可能性更小。Bob可不希望引导火箭着陆的代码中有bug!为确保万无一失,Bob决定计算两种算法在列表包含100个元素的情况下需要的时间。


假设检查一个元素需要1毫秒。使用简单查找时,Bob必须检查100个元素,因此需要100毫秒才能查找完毕。而使用二分查找时,只需检查7个元素(log2100大约为7),因此需要7毫秒就能查找完毕。然而,实际要查找的列表可能包含10亿个元素,在这种情况下,简单查找需要多长时间呢?二分查找又需要多长时间呢?请务必找出这两个问题的答案,再接着往下读。

 



Bob使用包含10亿个元素的列表运行二分查找,运行时间为30毫秒(log21 000 000 000大约为30)。他心里想,二分查找的速度大约为简单查找的15倍,因为列表包含100个元素时,简单查找需要100毫秒,而二分查找需要7毫秒。因此,列表包含10亿个元素时,简单查找需要30 × 15 = 450毫秒,完全符合在10秒内查找完毕的要求。Bob决定使用简单查找。这是正确的选择吗?


不是。实际上,Bob错了,而且错得离谱。列表包含10亿个元素时,简单查找需要10亿毫秒,相当于11天!为什么会这样呢?因为二分查找和简单查找的运行时间的增速不同。

 


运行时间的增速有天壤之别!

 

也就是说,随着元素数量的增加,二分查找需要的额外时间并不多,而简单查找需要的额外时间却很多。因此,随着列表的增长,二分查找的速度比简单查找快得多。Bob以为二分查找速度为简单查找的15倍,这不对:列表包含10亿个元素时,为3300万倍。有鉴于此,仅知道算法需要多长时间才能运行完毕还不够,还需知道运行时间如何随列表增长而增加。这正是大O表示法的用武之地。


大O表示法指出了算法有多快。例如,假设列表包含n个元素。简单查找需要检查每个元素,因此需要执行n次操作。使用大O表示法,这个运行时间为O(n)。单位秒呢?没有——大O表示法指的并非以秒为单位的速度。大O表示法让你能够比较操作数,它指出了算法运行时间的增速。


再来看一个例子。为检查长度为n的列表,二分查找需要执行log n次操作。使用大O表示法,这个运行时间怎么表示呢?O(log n)。一般而言,大O表示法像下面这样。

 

 

这指出了算法需要执行的操作数。之所以称为大O表示法,是因为操作数前有个大O。这听起来像笑话,但事实如此!


下面来看一些例子,看看你能否确定这些算法的运行时间。


1.3.2 理解不同的大O运行时间


下面的示例,你在家里使用纸和笔就能完成。假设你要画一个网格,它包含16个格子。

 


算法1 


一种方法是以每次画一个的方式画16个格子。记住,大O表示法计算的是操作数。在这个示例中,画一个格子是一次操作,需要画16个格子。如果每次画一个格子,需要执行多少次操作呢?

 


6个格子需要16步。这种算法的运行时间是多少?


算法2


请尝试这种算法——将纸折起来。



在这个示例中,将纸对折一次就是一次操作。第一次对折相当于画了两个格子!


再折,再折,再折。



折4次后再打开,便得到了漂亮的网格!每折一次,格子数就翻倍,折4次就能得到16个格子!

 


你每折一次,绘制出的格子数都翻倍,因此4步就能“绘制”出16个格子。这种算法的运行时间是多少呢?请搞清楚这两种算法的运行时间之后,再接着往下读。


答案如下:算法1的运行时间为O(n),算法2的运行时间为O(log n)。


1.3.3 大O表示法指出了最糟情况下的运行时间


假设你使用简单查找在电话簿中找人。你知道,简单查找的运行时间为O(n),这意味着在最糟情况下,必须查看电话簿中的每个条目。如果要查找的是Adit——电话簿中的第一个人,一次就能找到,无需查看每个条目。考虑到一次就找到了Adit,请问这种算法的运行时间是O(n)还是O(1)呢?


简单查找的运行时间总是为O(n)。查找Adit时,一次就找到了,这是最佳的情形,但大O表示法说的是最糟的情形。因此,你可以说,在最糟情况下,必须查看电话簿中的每个条目,对应的运行时间为O(n)。这是一个保证——你知道简单查找的运行时间不可能超过O(n)。


说明

除最糟情况下的运行时间外,还应考虑平均情况的运行时间,这很重要。最糟情况和平均情况将在第4章讨论。


1.3.4 一些常见的大O运行时间


下面按从快到慢的顺序列出了你经常会遇到的5种大O运行时间。


  • O(log n),也叫对数时间,这样的算法包括二分查找。

  • O(n),也叫线性时间,这样的算法包括简单查找。

  • O(n * log n),这样的算法包括第4章将介绍的快速排序——一种速度较快的排序算法。

  • O(n2),这样的算法包括第2章将介绍的选择排序——一种速度较慢的排序算法。

  • O(n!),这样的算法包括接下来将介绍的旅行商问题的解决方案——一种非常慢的算法。


假设你要绘制一个包含16格的网格,且有5种不同的算法可供选择,这些算法的运行时间如上所示。如果你选择第一种算法,绘制该网格所需的操作数将为4(log 16 = 4)。假设你每秒可执行10次操作,那么绘制该网格需要0.4秒。如果要绘制一个包含1024格的网格呢?这需要执行10(log 1024 = 10)次操作,换言之,绘制这样的网格需要1秒。这是使用第一种算法的情况。


第二种算法更慢,其运行时间为O(n)。即要绘制16个格子,需要执行16次操作;要绘制1024个格子,需要执行1024次操作。执行这些操作需要多少秒呢?

 

下面按从快到慢的顺序列出了使用这些算法绘制网格所需的时间:



还有其他的运行时间,但这5种是最常见的。


这里做了简化,实际上,并不能如此干净利索地将大O运行时间转换为操作数,但就目前而言,这种准确度足够了。等你学习其他一些算法后,第4章将回过头来再次讨论大O表示法。当前,我们获得的主要启示如下。


  • 算法的速度指的并非时间,而是操作数的增速。

  • 谈论算法的速度时,我们说的是随着输入的增加,其运行时间将以什么样的速度增加。

  • 算法的运行时间用大O表示法表示。

  • O(log n)比O(n)快,当需要搜索的元素越多时,前者比后者快得越多。


练习


使用大O表示法给出下述各种情形的运行时间。


1.3在电话簿中根据名字查找电话号码。

1.4在电话簿中根据电话号码找人。(提示:你必须查找整个电话簿。)

1.5阅读电话簿中每个人的电话号码。

1.6阅读电话簿中姓名以A打头的人的电话号码。这个问题比较棘手,它涉及第4章的概念。答案可能让你感到惊讶!


1.3.5 旅行商


阅读前一节时,你可能认为根本就没有运行时间为O(n!)的算法。让我来证明你错了!下面就是一个运行时间极长的算法。这个算法要解决的是计算机科学领域非常著名的旅行商问题,其计算时间增加得非常快,而有些非常聪明的人都认为没有改进空间。

 


有一位旅行商。


他需要前往5个城市。

这位旅行商(姑且称之为Opus吧)要前往这5个城市,同时要确保旅程最短。为此,可考虑前往这些城市的各种可能顺序。

 

对于每种顺序,他都计算总旅程,再挑选出旅程最短的路线。5个城市有120种不同的排列方式。因此,在涉及5个城市时,解决这个问题需要执行120次操作。涉及6个城市时,需要执行720次操作(有720种不同的排列方式)。涉及7个城市时,需要执行5040次操作!



 推而广之,涉及n个城市时,需要执行n!(n的阶乘)次操作才能计算出结果。因此运行时间为O(n!),即阶乘时间。除非涉及的城市数很少,否则需要执行非常多的操作。如果涉及的城市数超过100,根本就不能在合理的时间内计算出结果——等你计算出结果,太阳都没了。


这种算法很糟糕!Opus应使用别的算法,可他别无选择。这是计算机科学领域待解的问题之一。对于这个问题,目前还没有找到更快的算法,有些很聪明的人认为这个问题根本就没有更巧妙的算法。面对这个问题,我们能做的只是去找出近似答案,更详细的信息请参阅第10章。

最后需要指出的一点是,高水平的读者可研究一下二叉树,这在最后一章做了简要的介绍。


1.4 小结

  • 二分查找的速度比简单查找快得多。

  • O(log n)比O(n)快。需要搜索的元素越多,前者比后者就快得越多。

  • 算法运行时间并不以秒为单位。

  • 算法运行时间是从其增速的角度度量的。

  • 算法运行时间用大O表示法表示。


感谢图灵教育对本次活动的支持



版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/dQCFKyQDXYm3F8rB0/article/details/78628569

智能推荐

ad hoc是什么的简称_苹果ios签名有几种?分别什么价格?app分发内测有几种?-程序员宅基地

文章浏览阅读425次。随着经济的发展,苹果手机用户在不断的增加,苹果方面对于app上架也越来越严格,因此,很多app都上架不了。所以逼得很多app开发商不得不另外寻找出路,寻找其他能做苹果app分发下载的渠道。那么目前市场上关于苹果app内测分发的渠道有哪几种呢?接下来大家就和‘咕噜分发’小编一起来看一下。就目前市场上苹果分发的渠道来看,苹果app的分发下载主流主要有4种:AppStore,企业签名,超级签名,TF上架..._adhoc和tf

html页面整体隐藏,从html页面隐藏javascript / jquery脚本?-程序员宅基地

文章浏览阅读326次。最好的办法是在加载dom树后立即删除脚本标记,或者在javascript中动态创建脚本标记.无论哪种方式,如果有人想使用Web开发人员工具或Firebug,他们仍然会看到javascript.如果它在浏览器中,它将被看到.动态创建脚本标记的一个优点是,如果关闭javascript,则不会加载javascript.如果我关闭了javascript,我仍然可以在html中看到所有内容,因为您无法删除脚..._html隐藏脚本

搭建Ubuntu 10.04系统(嵌入式开发) _initrd.lz和vmlinuz下载-程序员宅基地

文章浏览阅读3.9k次。搭建Ubuntu 10.04系统(嵌入式开发) 1. 下载安装:1.1下载ubuntu:http://cdimage.ubuntu.com/releases/ 1.2 安装ubuntu:1.2.1 硬盘安装: (windows,硬盘安装ubuntu)------------ boot.ini: ------------------------[boot loader]timeout=10default=multi(0)disk(0)rdisk(0)partition(1)/WINDOWS[operatin_initrd.lz和vmlinuz下载

「Tensorflow」基于CNN的数字OCR识别_tensorflow ocr-程序员宅基地

文章浏览阅读1.9k次,点赞4次,收藏14次。导读对于人类来说,识别手写的数字是一件非常容易的事情。我们甚至不用思考,就可以看出下面的数字分别是1,2,3。本期将使用Tensorflow搭建卷积神经网络,进行手写数字的识别。代码可关注公众号 IamZLT,后台回复「手写数字识别」即可免费获取。本系列文章Part1:基于CNN的数字OCR识别part2:基于CNN的汉字识别预处理对于手写数字的初始图片如下所示。在搭建网络前我们需要对其进行预处理。▌读入图片并进行二值化图像._tensorflow ocr

数据结构笔记03 线性表_int function (sq)-程序员宅基地

文章浏览阅读215次。线性表定义:零个或多个【数据元素】的有限集合 抽象数据类型:(可以参考大话数据结构)ADT 线性表(List)Data ...Operation ...endADT 线性表的顺序存储结构、链式存储结构a. 顺序存储结构源码:#include#include#define MAXSIZE 20#define OK 1#define_int function (sq)

枚举、二分问题总结_二分枚举-程序员宅基地

文章浏览阅读1.6k次。枚举算法设计步骤:1.确定枚举对象2.逐一列举可能解3.逐一验证可能解例题:数组配对—枚举题目描述给你一个长度为n的数组和一个正整数k,问从数组中任选两个数使其和是k的倍数,有多少种选法对于数组a1=1 , a2=2 , a3=2而言:(a1,a2)和(a2,a1)被认为是同一种选法;(a1,a2)和(a1,a3)被认为是不同的选法。输入数据第一行有两个正整数n,k。n<..._二分枚举

随便推点

android应用程序安装后自动打开_android 安装应用并自动打开-程序员宅基地

文章浏览阅读8.5k次。GetBroadcast.registerReceiver(getApplicationContext());//注册广播,用于监听应用是否安装完成//安装apkIntent intent = new Intent(Intent.ACTION_VIEW);intent.setDataAndType(Uri.fromFile(new File(fileURL)),"applicati_android 安装应用并自动打开

大坑:git无法添加一个空的文件夹_git 文件夹没有内容不可以add 吗-程序员宅基地

文章浏览阅读2.3w次,点赞3次,收藏9次。楔子今天在github上创建了个有初始化选中Initialize this repository with a README(初始化本库)的空白工程,然后用git clone到本地。我本意想创建一个gradle规范的目录,于是创建了.gitignore , README.md, settings.gradle这几个标准的文件,然后通过如下的脚本创建标准的代码目录。task "create-d..._git 文件夹没有内容不可以add 吗

phpexcel 设置批注_PHPExcel-设置表格字体颜色背景样式、数据格式、对齐方式、添加图片、批注、文字块、合并拆分单元格、单元格密码保护...-程序员宅基地

文章浏览阅读591次。首先到phpexcel官网上下载最新的phpexcel类,下周解压缩一个classes文件夹,里面包含了PHPExcel.php和PHPExcel的文件夹,这个类文件和文件夹是我们需要的,把classes解压到你项目的一个目录中,重名名为phpexcel,开始喽,(代码都摘自自带实例)程序部分require_once'./phpexcel/PHPExcel.php';//首先创建一个新的对象..._phpexcel_style_fill

html的<c >循环,C标签之forEach-程序员宅基地

文章浏览阅读2.8k次。属 性描 述是否必须缺省值items进行循环的项目否无begin開始条件否0end结束条件否集合中的最后一个项目step步长否1var代表当前项目的变量名否无varStatus显示循环状态的变量否无varStatus 属性JSTL中的varStatus和 var 属性一样。varStatus 用于创建限定了作用域的变量。只是。由 varStatus 属性命名的变量并不存储当前索引值或当前元素,而是..._html foreach

动态规划专题:beginner_字典序最小的lis-程序员宅基地

文章浏览阅读676次。UVa 11584:看了这道题我才知道我的思维有多弱……纠结了好久…… 状态转移方程:d[i]=min{d[j-1]+1|str[j-->i]为回文串}。 LA4256:水题一道,可我又搞了半天!就因为少记录了一维! 状态转移方程为:d[i][u]=min{d[i+1][v]|u,v相连},如果u!=原串的第i个数,再加上1。 UVa 105_字典序最小的lis

ecplise 如何导入包到web app library-程序员宅基地

文章浏览阅读545次。2019独角兽企业重金招聘Python工程师标准>>> ..._ecplise web app libary