AIGC革命已来,如何在企业场景落地?如何选择模型、怎样应用RAG、需要哪些组织流程配套? 了解详情
写点什么

算法图解之算法简介

  • 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:52818

评论

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

#滴滴夜莺# Nightingale & Prometheus

漂洋散人

Docker 常用命令,还有谁不会?

xcbeyond

Docker 常用命令 28天写作

这个新春,你的云端安全守卫来咯 | 新服务上线

亚马逊云科技 (Amazon Web Services)

前端上手Docker超详细基础教程

1024肥宅

Docker Linux 大前端 jenkins CI/CD

真实字节二面:什么是伪共享?

艾小仙

Java 程序员 字节跳动 面试

手写一个LRU缓存淘汰算法

Simon郎

Java 大数据 缓存 LRU 数据结构与算法

敏捷, 是一种信仰

boshi

敏捷 七日更 28天写作

别梦依稀咒逝川,Ruby二十八年前|M1芯片Mac os系统配置Ruby(3.0.0) on Rails(6.1.1)开发环境(2021最新攻略)

刘悦的技术博客

ruby ruby-on-rails rubygems macOS Big Sur m1

环信大学 | 构建一套适合微服务的高可用架构

DT极客

代码从业者

ES_her0

28天写作 3月日更

VR,正在上演一出“风月宝鉴”

脑极体

一线互联网大厂面经分享:阿里三面+头条四面+腾讯二面+美团四面

Java架构之路

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

打破垄断 上海发布自主研发树图区块链重大成果

CECBC

区块链

java学习笔记(一)

陈皮

Java

面试系列二:精选大数据面试真题JVM专项-附答案详细解析

五分钟学大数据

大数据 28天写作 3月日更

星环科技Sophon Edge边缘计算平台持续赋能千家万业

星环科技

谁才是一级方程式赛车中的最强车手?

亚马逊云科技 (Amazon Web Services)

七种分布式事务的解决方案,一次讲给你听

moon聊技术

图解CyclicBarrier运动员接力赛

叫练

面试 AQS CyclicBarrier

「两次遍历」要比「一次遍历」要慢 ... 为啥呀?为啥呀??

宫水三叶的刷题日记

面试 LeetCode 数据结构与算法

加快布局区块链技术发展,助力网络强国建设

CECBC

区块链

javascript中的内存管理

程序那些事

JavaScript nodejs 内存管理 程序那些事

产品经理训练营 - 第四章作业 (二)

joelhy

产品经理训练营

「产品经理训练营」作业 05:知识星球加入星球流程图

狷介

产品经理训练营

SuperBenchmarker sb在mac上的安装手记

edd

数据库周刊59丨GaussDB(for openGauss)开放商用;人大金仓保障冬奥会演练顺利完成;MDL锁导致的MySQL问题分析;PG日志使用手册;达梦表空间查询;数据库笔试题面试题集……

墨天轮

MySQL 数据库 程序员 运维 postgre

SQL Server 多表数据增量获取和发布 2.1

happlyfox

28天写作 3月日更

(28DW-S8-Day10) T型学习模式:迁移式学习

mtfelix

T型人才 28天写作 迁移学习 一万小时定律

Kubelet从入门到放弃:拓扑管理(上)

DCOS

Linux Kubernetes 云原生 kubelet

想做技术自媒体实现财富自由?先看看广告报价吧,无编码学爬虫之二。

梦想橡皮擦

Python 28天写作 2月春节不断更 3月日更

2021年美团/字节跳动/腾讯面经总结:互联网工程师必备的面试1000题

比伯

Java 编程 程序员 架构 面试

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