【QCon】精华内容上线92%,全面覆盖“人工智能+”的典型案例!>>> 了解详情
写点什么

算法图解之算法简介

  • 2019-10-15
  • 本文字数:6791 字

    阅读完需:约 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 = 0high = len(list) - 1
复制代码



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


mid = (low + high) / 2  ←---如果(low + high)不是偶数,Python自动将mid向下取整。guess = list[mid]
复制代码


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


if guess < item:  low = mid + 1
复制代码



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


def binary_search(list, item):  low = 0    (以下2行)low和high用于跟踪要在其中查找的列表部分  high = len(list)—1    while low <= high:  ←-------------只要范围没有缩小到只包含一个元素,    mid = (low + high) / 2  ←-------------就检查中间的元素    guess = list[mid]    if guess == item:  ←-------------找到了元素      return mid    if guess > item:  ←-------------猜的数字大了      high = mid - 1    else:  ←---------------------------猜的数字小了      low = mid + 1  return None  ←--------------------没有指定的元素my_list = [1, 3, 5, 7, 9]  ←------------来测试一下!print binary_search(my_list, 3) # => 1  ←--------------------别忘了索引从0开始,第二个位置的索引为1print binary_search(my_list, -1) # => None  ←--------------------在Python中,None表示空,它意味着没有找到指定的元素
复制代码


练习


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 个格子。如果每次画一个格子,需要执行多少次操作呢?



画 16 个格子需要 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 表示法表示。


本文内容来自作者图书作品《算法图解》,点击购买


2019-10-15 19:52828

评论

发布
暂无评论
发现更多内容

内存数据库解析与主流产品对比(三)

星环科技

数据库 大数据

数据库恢复子系统的常见技术和方案对比(二)

星环科技

数据库 大数据

新思科技发布《美国不良软件质量成本:2020年报告》

InfoQ_434670063458

软件质量 新思科技

30天消化MyBatis源码解析笔记,吊打面试官,offer接到手软

Java架构之路

Java 程序员 架构 面试 编程语言

一个 3 年 Java 程序员 5 家大厂的面试总结(已拿Offer)

Java架构之路

Java 程序员 架构 面试 编程语言

Alibaba最新产物手册宝典:分布式核心原理解析,简直是Java程序员福音!

996小迁

Java 架构 面试 分布式

一文读懂Java动态代理

潘大壮

Java jdk 动态代理

从零开始学习Git

ITCamel

git

产品训练营--第二期作业

曦语

产品训练营

智能汽车为什么新势力有胜算(28天写作 Day20/28)

mtfelix

28天写作 新能源汽车 智能汽车 造车新势力

抽奖助手利益相关方

千竹

关注直播 走近滴滴夜莺K8S监控组件

滴滴云

k8s 滴滴技术 监控告警 滴滴夜莺

译文《最常见的10种Java异常问题》

潘大壮

Java 异常 java异常处理 Exception

《程序员修炼之道》- 务实的哲学(3)

石云升

读书笔记 程序员 28天写作 批判性思维 完成好过完美

10 个 JavaScript 简洁代码小技巧(文末彩蛋)

零和幺

JavaScript 大前端 CleanCode

阿里四年技术 TL 的得失总结:如何做好技术 Team Leader

阿里巴巴云原生

云计算 项目管理 程序员 微服务 云原生

Redis核心剖析:为什么这么“快”的秘密

Java架构师迁哥

厌倦了EXCEL想玩点新花样?教你利用Python做数据筛选(下)

智分析

Python

数据库恢复子系统的常见技术和方案对比(一)

星环科技

数据库 大数据

【推荐收藏!】Gradle 与 Android 构建入门

百度Geek说

研发工具 andiod

拍乐云 Flutter SDK 全新发布,跨平台音视频开发更easy

拍乐云Pano

flutter 音视频 WebRTC RTC

滴滴开源Logi-KafkaManager 一站式Kafka监控与管控平台

滴滴云

kafak 滴滴开源 监控告警 运维平台

内存数据库解析与主流产品对比(一)

星环科技

数据库 大数据

一周信创舆情观察(1.18~1.24)

统小信uos

kotlin高阶函数let、with、apply、run、also使用场景

陈吉米

kotlin

区区一个SpringBoot问题就干趴下了?我却凭着这套“神级PDF文档”吊打面试官

Java 编程 面试 微服务

5年Java经验不会源码被拒,苦学这些Spring源码笔记后,面试不再慌

Java架构之路

Java 程序员 架构 面试 编程语言

内存数据库解析与主流产品对比(二)

星环科技

数据库

译文《全新首发JDK 16全部新特性》

潘大壮

Java jdk JVM

Flink 学习路线总结

大数据学习指南

大数据 flink

Elasticsearch 基于脚本进行 partial update

escray

elastic 七日更 28天写作 死磕Elasticsearch 60天通过Elastic认证考试

算法图解之算法简介_语言 & 开发_Aditya Bhargava_InfoQ精选文章