本文共 2950 字,大约阅读时间需要 9 分钟。
本文来源 | 《算法图解:像小说一样有趣的算法入门书》
作者 | Aditya Bhargava
责编 | 林瑟
我一个非程序员,买了这本《算法图解》的书在看,刚拆快递后翻了一会,被我老板给看到了,被她强行借走去翻了,说很有意思,翻了几天才还我。。。如果你是下面中任何一种类型的同学,请继续往下看:
业余程序员
编程培训班学员
需要重温算法的计算机专业毕业生
对编程感兴趣的物理或数学等专业毕业生
算法是一组完成任务的指令。任何代码片段都可视为算法,但这里我们只介绍比较有趣的部分,比如,二分查找。
假设要在电话簿中找一个名字以 K 打头的人,现在谁还用电话簿!可以从头开始翻页,直到进入以 K 打头的部分。但你很可能不这样做,而是从中间开始,因为你知道以 K 打头的名字在电话簿中间。
现在假设你登录 Facebook。当你这样做时,Facebook 必须核实你是否有其网站的账户,因此必须在其数据库中查找你的用户名。如果你的用户名为 karlmageddon,Facebook 可从以 A 打头的部分开始查找,但更合乎逻辑的做法是从中间开始查找。
这是一个查找问题,在前述所有情况下,都可使用同一种算法来解决问题,这种算法就是二分查找。
二分查找是一种算法,其输入是一个有序的元素列表(必须有序的原因稍后解释)。如果要查找的元素包含在列表中,二分查找返回其位置;否则返回null。
下图是一个例子。
下面的示例说明了二分查找的工作原理。我随便想一个1~100的数字。
你的目标是以最少的次数猜到这个数字。你每次猜测后,我会说小了、大了或对了。
假设你从1开始依次往上猜,猜测过程会是这样。
这是简单查找,更准确的说法是傻找。每次猜测都只能排除一个数字。如果我想的数字是 99,你得猜 99 次才能猜到!
01
更佳的查找方式
下面是一种更佳的猜法。从 50 开始。
小了,但排除了一半的数字!至此,你知道 1~50 都小了。接下来,你猜75。
大了,那余下的数字又排除了一半!使用二分查找时,你猜测的是中间的数字,从而每次都将余下的数字排除一半。接下来,你猜 63(50 和 75 中间的数字)。
这就是二分查找,你学习了第一种算法!每次猜测排除的数字个数如下。
不管我心里想的是哪个数字,你在 7 次之内都能猜到,因为每次猜测都将排除很多数字!
假设你要在字典中查找一个单词,而该字典包含 240000 个单词,你认为每种查找最多需要多少步?
如果要查找的单词位于字典末尾,使用简单查找将需要 240000 步。使用二分查找时,每次排除一半单词,直到最后只剩下一个单词。
因此,使用二分查找只需 18 步——少多了!一般而言,对于包含 n 个元素的列表,用二分查找最多需要 log2n 步,而简单查找最多需要 n 步。
02
对数
你可能不记得什么是对数了,但很可能记得什么是幂。log10100相当于问“将多少个10相乘的结果为100”。答案是两个:10 × 10 = 100。因此,log10100 = 2。对数运算是幂运算的逆运算。
对数是幂运算的逆运算
本文使用大O表示法(稍后介绍)讨论运行时间时,log 指的都是 log2。使用简单查找法查找元素时,在最糟情况下需要查看每个元素。
而使用二分查找时,最多需要检查 log n个元素。如果列表包含 8 个元素,你最多需要检查 3 个元素,因为 log 8 = 3(23 = 8)。如果列表包含1024个元素,你最多需要检查10个元素,因为 log 1024 = 10(210 =1024)。
下面来看看如何编写执行二分查找的 Python 代码。你只需知道,可将一系列元素存储在一系列相邻的桶(bucket),即数组中。这些桶从0开始编号:第一个桶的位置为#0,第二个桶为#1,第三个桶为#2,以此类推。
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表示空,它意味着没有找到指定的元素
下面就是一个运行时间极长的算法。这个算法要解决的是旅行商问题,其计算时间增加得非常快,而有些非常聪明的人都认为没有改进空间。
有一位旅行商,他需要前往5个城市。
这位旅行商(姑且称之为 Opus 吧)要前往这5个城市,同时要确保旅程最短,为此,可考虑前往这些城市的各种可能顺序。
若按旅程最短的路线来选,5 个城市有 120 种不同的排列方式。因此,解决这个问题需要执行 120 次操作。涉及 6 个城市时,需要执行 720 次操作,依次递增!
推而广之,涉及 n 个城市时,需要执行 n!(n 的阶乘)次操作才能计算出结果。因此运行时间为 O(n!),即阶乘时间。
这种算法很糟糕!这是计算机科学领域待解的问题之一。对于这个问题,目前还没有找到更快的算法,有些很聪明的人认为这个问题根本就没有更巧妙的算法。
面对这个问题,我们能做的只是去找出近似答案,高水平的读者可以在《算法图解:像小说一样有趣的算法入门书》中研究一下二叉树!!
扫描下方二维码阅读全书
▼
点击阅读原文,学习算法也可以很有趣!!
点个在看
学算法不秃头
↓↓
转载地址:http://vzspi.baihongyu.com/