01-算法简介

本章内容

• 了解算法
• 编写第一种查找算法 —— 二分查找
• 算法的运行时间 —— 大O表示法
• 了解一种常用算法设计 —— 递归
• 为什么要学习算法与数据结构

了解算法

算法是一组完成任务的指令。任何代码片段都视为算法。

• 学习算法，学习比较不同算法的优缺点
  • 不同场景下该使用快排还是合并排序？
  • 该使用数组还是链表？

使用不同的算法或仅仅改用不同的数据结构，结果可能就大不相同。

• 学习问题解决技巧
  • 学习到一些广泛使用的算法
  • 基于此，进阶去学习更具体的AI算法，数据库算法等

二分查找

场景描述

假设要在电话簿中找一个名字以K打头的人,可以从头开始翻页，直到进入以K打头的部分。但你很可能不这样做，而是从中间开始，因为你知道以K打头的名字在电话簿中间。 又假设要在字典中找一个以O打头的单词，你也将从中间附近开始。 乎逻辑的做法是从中间开始查找。 现在假设你登录Facebook。当你这样做时，Facebook必须核实你是否有其网站的账户，因此必须在其数据库中查找你的用户名。如果你的用户名为karlmageddon，Facebook可从以A打头的部分开始查找，但更合乎逻辑的做法是从中间开始查找。 这是一个查找问题，在前述所有情况下，都可使用同一种算法来解决问题，这种算法就是二分查找。

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

工作原理

随意想一个 1 到 100 的数字。

目标以最少次数猜到这个数字，每次猜测后，会反馈小了或者大了。

1. 如果从1开始依次向上找 —— 简单查找（傻找），每次猜测只能排除一个数字，如果想的数字是 99，就得99次。
2. 如果从 50 开始， 大了就猜 75 … 每次排除一半 —— 二分查找 | 100 个元素： | 50 | 25 | 13 | 7 | 4 | 2 | 1 | | —- | —- | —- | —- | —- | —- | —- | —- | | 步数： | 1 | 2 | 3 | 4 | 5 | 6 | 7 |

7 步之内必能找到。

一般而言，对于包含 n 个元素的列表，二分查找最多需要 ㏒₂n 步， 简单查找最多需要 n 步。

思考

1. 无序会怎么样？

2. 无序能用什么算法？

   练习

3. 假设有一个包含128个名字的有序列表，使用二分查找去查询一个名字最多需要几步？列表长度翻倍呢？

4. 代码实现

大O表示法

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

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

场景描述

Bob要为NASA编写一个查找算法，这个算法在火箭即将登陆月球前开始执行，帮助计算着陆地点。 这个示例表明，两种算法的运行时间呈现不同的增速。Bob需要做出决定，是使用简单查找还是二分查找。使用的算法必须快速而准确。一方面，二分查找的速度更快。Bob必须在10秒钟内找出着陆地点，否则火箭将偏离方向。另一方面，简单查找算法编写起来更容易，因此出现bug的可能性更小。Bob可不希望引导火箭着陆的代码中有bug！为确保万无一失,Bob决定计算两种算法在列表包含100个元素的情况下需要的时间。 假设检查一个元素需要1毫秒。使用简单查找时，Bob必须检查100个元素，因此需要100毫秒才能查找完毕。而使用二分查找时，只需检查7个元素（ ㏒₂100大约为7)，因此需要7毫秒就能查找完毕。然而，实际要查找的列表可能包含10亿个元素，在这种情况下，简单查找需要多长时间呢？二分查找又需要多长时间呢？请务必找出这两个问题的答案，再接着往下读。

二分查找：㏒₂1 000 000 000
简单查找：10亿毫秒

Bob使用包含10亿个元素的列表运行二分查找，运行时间为30毫秒（ ㏒₂1 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(n) O-> ‘大O’ n-> 操作数

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

理解不同的大O运行时间

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

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

画16个格子需要16步。这种算法的运行时间是多少?
算法2
请尝试这种算法——将纸折起来。

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

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

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

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

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

一些常见的大O运行时间

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

1. O (log n )，也叫对数时间 ，这样的算法包括二分查找。
2. O (n )，也叫线性时间 ，这样的算法包括简单查找。
3. O (n log n )，这样的算法包括第4章将介绍的快速排序* —— 一种速度较快的排序算法。
4. O (n 2 )，这样的算法包括第2章将介绍的选择排序 —— 一种速度较慢的排序算法。
5. O (n !)，这样的算法包括接下来将介绍的旅行商问题的解决方案 —— 一种非常慢的算法。

主要启示

• 算法的速度指的并非时间，而是操作数的增速。
• 谈论算法的速度时，我们说的是随着输入的增加，其运行时间将以什么样的速度增加。
• 算法的运行时间用大O表示法表示。
• O (log n )比O (n )快，当需要搜索的元素越多时，前者比后者快得越多。

练习

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

• 在电话簿中根据名字查找电话号码。
• 在电话簿中根据电话号码找人。(提示:你必须查找整个电话簿。)
• 阅读电话簿中每个人的电话号码。
• 阅读电话簿中姓名以A打头的人的电话号码。

旅行商

运行时间极长的算法。这个算法要解决的是计算机科学领域非常著名的旅行商问题，其计算时间增加得非常快， 而有些非常聪明的人都认为没有改进空间。大O表示：O (n !)

场景描述

有一位旅行商。 他需要前往5个城市。 这位旅行商(姑且称之为Opus吧)要前往这5个城市，同时要确保旅程最短。为此，可考虑前往这些城市的各种可能顺序。 对于每种顺序，他都计算总旅程，再挑选出旅程最短的路线。5个城市有120种不同的排列方式。因此，在涉及5个城市时，解决这个问题需要执行120次操作。涉及6个城市时，需要执行720次操作(有720种不同排列方式)。涉及7个城市时，需要执行5040次操作! 推而广之，涉及n 个城市时，需要执行n !(n 的阶乘)次操作才能计算出结果。因此运行时间为O (n !)，即阶乘时间。除非涉及的城市数很少，否则需要执行非常多的操作。如果涉及的城市数超过100，根本就不能在合理的时间内计算出结果——等你计算出结果，太阳都没了。