算法简介

• 为阅读后续内容打下基础
• 编写第一种查找算法--二分查找
• 学习如何表示算法运行时间--大O表示法

引言

算法是一组完成任务的指令。任何代码片段都可视为算法，但我们只介绍比较有趣的部分。要么速度快，要么能解决有趣的问题，要么兼而有之。

对于每种算法，都将首先进行描述并提供示例，再使用大O表示法讨论其运行时间，最后探索它可以解决的其他问题

二分查找

二分查找是一种算法，其输入是一个有序的元素列表。如果要查找的元素包含在列表中，二分查找返回其位置；否则返回null。

二分查找每一次都能排除掉一半数据，一般而言，对于包含n个元素的列表，用二分查找最多需要\(log_2n\)步，而简单查找最多需要n步。

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 ←--------------------没有指定的元素

仅当列表是有序的时候，二分查找才管用。例如，电话簿中的名字是按字母顺序排列的，因此可以使用二分查找来查找名字。如果名字不是按顺序排列的，结果将如何呢？

运行时间

简单查找逐个地检查数字，如果列表包含100个数字，最多需要猜100次。如果列表包含40亿个数字，最多需要猜40亿次。换言之，最多需要猜测的次数与列表长度相同，这被称为线性时间（linear time）。

二分查找则不同。如果列表包含100个元素，最多要猜7次；如果列表包含40亿个数字，最多需猜32次。厉害吧？二分查找的运行时间为对数时间（或log时间）。

大O表示法

大O表示法是一种特殊的表示法，指出了算法的速度有多快。

运行时间的增加速度

仅知道算法需要多长时间才能运行完毕还不够，还需知道运行时间如何随列表增长而增加。这正是大O表示法的用武之地

大O表示法指出了算法有多快。例如，假设列表包含n 个元素。简单查找需要检查每个元素，因此需要执行n 次操作。使用大O表示法，这个运行时间为O(n)。单位秒呢？没有——大O表示法指的并非以秒为单位的速度。大O表示法让你能够比较操作数，它指出算法运行时间的增速。

之所以称为大O表示法，是因为操作数前有个大O。这听起来像笑话，但事实如此！

最坏运行时间

简单查找的运行时间总是为O(n)。一次就找到了，这是最佳的情形，但大O表示法说的是最糟的情形。因此，你可以说，在最糟情况下，必须查看每个条目，对应的运行时间为O(n)。这是一个保证——你知道简单查找的运行时间不可能超过O(n)。

除最糟情况下的运行时间外，还应考虑平均情况的运行时间，这很重要。

常见大O运行时间

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

还有其他的运行时间，但这5种是最常见的。

旅行商问题

有一位旅行商。他需要前往5个城市。同时要确保旅程最短。为此，可考虑前往这些城市的各种可能顺序。

5个城市有120种不同的排列方式。因此，在涉及5个城市时，解决这个问题需要执行120次操作。涉及6个城市时，需要执行720次操作

如果涉及的城市数超过100，根本就不能在合理的时间内计算出结果——等你计算出结果，太阳都没了。

这是计算机科学领域待解的问题之一。对于这个问题，目前还没有找到更快的算法，有些很聪明的人认为这个问题根本就没有更巧妙的算法。

小结

• 二分查找的速度比简单查找快得多。
• O(log n)比O(n)快。需要搜索的元素越多，前者比后者就快得越多。
• 算法运行时间并不以秒为单位。
• 算法运行时间是从其增速的角度度量的。
• 算法运行时间用大O表示法表示

如果你在哪儿卡住了，可以到这里查看源码。