因为简单！我的第一本算法书，就被女友抢走了……

fvhPHALo

普通程序员，不学算法，也可以成为大神吗？对不起，这个，绝对不可以。
; Z  p, _5 x& B9 a. n( {
可是算法好难啊~~看两页书就想睡觉……所以就不学了吗？就一直当普通程序员吗？
' j8 ]/ r1 [. E* i. x, i' B" S如果有一本算法书，看着很轻松……又有代码示例……又有讲解……
怎么会有那样的书呢？哎呀，最好学了算法人还能变得很萌……
- y. x0 _# z' P+ ]: t$ G这个……要求是不是太高了呀？哈哈，有的书真的能满足所有这些要求哦！
来，看看这本书有多可爱——

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

又假设要在字典中找一个以O打头的单词，你也将从中间附近开始。
6 V" @  G* Q. y0 u. S4 a# V现在假设你登录Facebook。当你这样做时，Facebook必须核实你是否有其网站的账户，因此必须在其数据库中查找你的用户名。如果你的用户名为karlmageddon，Facebook可从以A打头的部分开始查找，但更合乎逻辑的做法是从中间开始查找。
. e7 h) v, D) K) G这是一个查找问题，在前述所有情况下，都可使用同一种算法来解决问题，这种算法就是二分查找。

) n8 w* C1 `  r2 w9 V0 G1 T7 o二分查找是一种算法，其输入是一个有序的元素列表（必须有序的原因稍后解释）。如果要查找的元素包含在列表中，二分查找返回其位置；否则返回null。
, v) C* j+ s" H# l下图是一个例子。

下面的示例说明了二分查找的工作原理。我随便想一个1～100的数字。
: {$ u% }5 o! a
你的目标是以最少的次数猜到这个数字。你每次猜测后，我会说小了、大了或对了。
* n$ Q- n) \3 I* A4 n/ E6 v2 w' M假设你从1开始依次往上猜，猜测过程会是这样。

这是简单查找，更准确的说法是傻找。每次猜测都只能排除一个数字。如果我想的数字是99，你得猜99次才能猜到！
更佳的查找方式
4 m0 }6 ^2 U- p. j+ Y8 V+ j: F, a
下面是一种更佳的猜法。从50开始。
* }- X# U5 V+ n: Q9 x( l3 |
( t3 o0 C- Z; K/ R8 G7 p3 C小了，但排除了一半的数字！至此，你知道1～50都小了。接下来，你猜75。
  v+ w) M% C, X
大了，那余下的数字又排除了一半！使用二分查找时，你猜测的是中间的数字，从而每次都将余下的数字排除一半。接下来，你猜63（50和75中间的数字）。

这就是二分查找，你学习了第一种算法！每次猜测排除的数字个数如下。
1 G  V& p' q6 F4 ~
6 N7 K* O4 g4 ~+ y$ J8 [不管我心里想的是哪个数字，你在7次之内都能猜到，因为每次猜测都将排除很多数字！
假设你要在字典中查找一个单词，而该字典包含240 000个单词，你认为每种查找最多需要多少步？

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

因此，使用二分查找只需18步——少多了！一般而言，对于包含n个元素的列表，用二分查找最多需要log2n步，而简单查找最多需要n步。
9 Z  ^' T+ X7 l" g7 d5 h8 p8 ?% }对数
% [9 z5 P- S9 P3 {# ^% M你可能不记得什么是对数了，但很可能记得什么是幂。log10100相当于问“将多少个10相乘的结果为100”。答案是两个：10 × 10 = 100。因此，log10100 = 2。对数运算是幂运算的逆运算。
! m% }" M2 _" {9 {' x2 k# k/ O5 ^
  M# ^* Q4 ]0 ?1 m- }- E对数是幂运算的逆运算
7 E# T, e( ]' S本书使用大O表示法（稍后介绍）讨论运行时间时，log指的都是log2。使用简单查找法查找元素时，在最糟情况下需要查看每个元素。因此，如果列表包含8个数字，你最多需要检查8个数字。而使用二分查找时，最多需要检查log n个元素。如果列表包含8个元素，你最多需要检查3个元素，因为log 8 = 3（23 = 8）。如果列表包含1024个元素，你最多需要检查10个元素，因为log 1024 = 10（210 =1024）。
+ j7 ?' \. E; I' \下面来看看如何编写执行二分查找的Python代码。这里的代码示例使用了数组。如果你不熟悉数组，也不用担心，下一章就会介绍。你只需知道，可将一系列元素存储在一系列相邻的桶（bucket），即数组中。这些桶从0开始编号：第一个桶的位置为#0，第二个桶为#1，第三个桶为#2，以此类推。
函数binary_search接受一个有序数组和一个元素。如果指定的元素包含在数组中，这个函数将返回其位置。你将跟踪要在其中查找的数组部分——开始时为整个数组。
0 u! A8 {1 G0 j7 Rlow = 0high = len(list) - 1
你每次都检查中间的元素。
mid = (low + high) / 2 ←---如果(low + high)不是偶数，Python自动将mid向下取整。guess = list[mid]ifguess < item: low = mid + 1如果猜的数字大了，就修改high。完整的代码如下。
whilelow  1 ←别忘了索引从0开始，第二个位置的索引为1print binary_search(my_list, -1) # => None ←在Python中，None表示空，它意味着没有找到指定的元素运行时间

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

回到前面的二分查找。使用它可节省多少时间呢？简单查找逐个地检查数字，如果列表包含100个数字，最多需要猜100次。如果列表包含40亿个数字，最多需要猜40亿次。换言之，最多需要猜测的次数与列表长度相同，这被称为线性时间（linear time）。
2 s4 a0 H" n( h4 H) V: J+ S) ~8 D% d二分查找则不同。如果列表包含100个元素，最多要猜7次；如果列表包含40亿个数字，最多需猜32次。厉害吧？二分查找的运行时间为对数时间（或log时间）。下表总结了我们发现的情况。
; Z- ?; V4 @! A. r& T) ?5 l
  y2 p+ K2 y! G2 B5 u. ?# ~
: Q3 y( |3 B) }9 R# h大O表示法
大O表示法是一种特殊的表示法，指出了算法的速度有多快。谁在乎呢？实际上，你经常要使用别人编写的算法，在这种情况下，知道这些算法的速度大有裨益。本节将介绍大O表示法是什么，并使用它列出一些最常见的算法运行时间。
算法的运行时间以不同的速度增加

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

% k- V6 c# m2 X; ]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表示法的用武之地。
& P' |$ Z3 }6 L; u. S, r" g* e
  h/ C+ }+ v: o1 Y3 H大O表示法指出了算法有多快。例如，假设列表包含n 个元素。简单查找需要检查每个元素，因此需要执行n 次操作。使用大O表示法，这个运行时间为O(n)。单位秒呢？没有——大O表示法指的并非以秒为单位的速度。大O表示法让你能够比较操作数，它指出了算法运行时间的增速。
再来看一个例子。为检查长度为n 的列表，二分查找需要执行log n 次操作。使用大O表示法，这个运行时间怎么表示呢？O(log n)。一般而言，大O表示法像下面这样。

这指出了算法需要执行的操作数。之所以称为大O表示法，是因为操作数前有个大O。这听起来像笑话，但事实如此！
下面来看一些例子，看看你能否确定这些算法的运行时间。
; }* R& E# t& C: l2 T6 h理解不同的大O运行时间

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

算法1
一种方法是以每次画一个的方式画16个格子。记住，大O表示法计算的是操作数。在这个示例中，画一个格子是一次操作，需要画16个格子。如果每次画一个格子，需要执行多少次操作呢？
- p6 w% d0 q0 |% t: i' g; V4 g
画16个格子需要16步。这种算法的运行时间是多少？
算法2
( G" o. n2 a4 A3 y请尝试这种算法——将纸折起来。

0 z2 G& _5 L1 C" |( d/ O- g( j( H在这个示例中，将纸对折一次就是一次操作。第一次对折相当于画了两个格子！
, d" g4 C. w  O+ T4 Y% p再折，再折，再折。

- O# a+ f3 M; ^: t$ m折4次后再打开，便得到了漂亮的网格！每折一次，格子数就翻倍，折4次就能得到16个格子！
) F$ g1 m, I; N' T' x# N
你每折一次，绘制出的格子数都翻倍，因此4步就能“绘制”出16个格子。这种算法的运行时间是多少呢？请搞清楚这两种算法的运行时间之后，再接着往下读。
答案如下：算法1的运行时间为O(n)，算法2的运行时间为O(log n)。
( K+ I9 z& \& r3 T大O表示法指出了最糟情况下的运行时间
; h. F1 v  m0 J+ }. D
6 m0 q$ c2 c# M& S: d7 r* ~- r假设你使用简单查找在电话簿中找人。你知道，简单查找的运行时间为O(n)，这意味着在最糟情况下，必须查看电话簿中的每个条目。如果要查找的是Adit——电话簿中的第一个人，一次就能找到，无需查看每个条目。考虑到一次就找到了Adit，请问这种算法的运行时间是O(n)还是O(1)呢？
简单查找的运行时间总是为O(n)。查找Adit时，一次就找到了，这是最佳的情形，但大O表示法说的是最糟的情形。因此，你可以说，在最糟情况下，必须查看电话簿中的每个条目，对应的运行时间为O(n)。这是一个保证——你知道简单查找的运行时间不可能超过O(n)。

说明
除最糟情况下的运行时间外，还应考虑平均情况的运行时间，这很重要。最糟情况和平均情况将在第4章讨论。
: ?: Q! {/ @* H( q" g# p5 {; t

一些常见的大O运行时间
) M5 ~( T3 W4 v. [; m! s; D
5 b; H  h/ X4 }下面按从快到慢的顺序列出了你经常会遇到的5种大O运行时间。
; |" l$ B5 T# s: w

2 z7 z, K! Z1 W0 D4 D) t1 T7 ^
• O(log n)，也叫对数时间，这样的算法包括二分查找。
  $ e6 O' A; l; m! ~: D0 _9 ?
• O(n)，也叫线性时间，这样的算法包括简单查找。
  ) I; r/ I; I5 i
• O(n * log n)，这样的算法包括第4章将介绍的快速排序——一种速度较快的排序算法。
  ( ]' u" ^" J6 ~5 W; n1 e
• 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次操作。执行这些操作需要多少秒呢？
  P, Y4 a- [- A+ v下面按从快到慢的顺序列出了使用这些算法绘制网格所需的时间：

还有其他的运行时间，但这5种是最常见的。
这里做了简化，实际上，并不能如此干净利索地将大O运行时间转换为操作数，但就目前而言，这种准确度足够了。等你学习其他一些算法后，第4章将回过头来再次讨论大O表示法。当前，我们获得的主要启示如下。
* n0 x$ W6 u' F- E( k' g, B

• 算法的速度指的并非时间，而是操作数的增速。
  1 {0 L" ~4 @: d% a+ X7 h2 f# K
• 谈论算法的速度时，我们说的是随着输入的增加，其运行时间将以什么样的速度增加。
  * }5 @) H& B: ?5 i% O5 x
• 算法的运行时间用大O表示法表示。
  
• O(log n)比O(n)快，当需要搜索的元素越多时，前者比后者快得越多。
  0 s0 f4 y' Z  m7 h/ g, O' |

以上内容来自《算法图解》

! v3 a. T1 W5 E8 N) D) _) J《算法图解》
( u- e! V- ]9 m1 F' v$ N
- a! {# m& i5 T+ p3 }( R  L, }2 ?3 o扫码查看详情

. g  H2 E, G- \9 K$ v/ f编辑推荐：
; F4 b0 X" |7 y& C2 _本书示例丰富，图文并茂，以让人容易理解的方式阐释了算法，旨在帮助程序员在日常项目中更好地发挥算法的能量。书中的前三章将帮助你打下基础，带你学习二分查找、大O表示法、两种基本的数据结构以及递归等。余下的篇幅将主要介绍应用广泛的算法，具体内容包括：面对具体问题时的解决技巧，比如，何时采用贪婪算法或动态规划；散列表的应用；图算法；K最近邻算法。
扫码或者点击阅读原文购买
- ~. I  G0 {. Q0 {
0 H: ^9 B- G' C4 |+ c/ I
作为码书商店的运营人员，诚邀你们进入我们的“CSDN码书福利群”，群里会不定时的给大家赠书书籍、优惠券等，有书籍推荐或者物流方面信息也可群里咨询~目前群已满100人，需要加群的请扫下方二维码添加微信，拉你入群哦~对此次活动不了解的也可咨询~



/ Q& F0 S6 F8 x( f7 X来源：http://www.yidianzixun.com/article/0MIo0Rxx
" X- J/ Q" o- h* {免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！