算法简介

本书说明，与算法基础概念

引言

本书是对Manning出版社的《Grokking Algorithms》一书的要点归纳与补充扩展。

本书图片均出自于原书，仅用于非商业目的，个人学习引用，根据引用协议在此做统一声明，copyright Manning Publications, drawn by adit.io

本书所有代码选择Python语言，若需要更多语言版本请前往Grokking Algorithms官方仓库。

算法是一组完成任务的指令。任何代码片段都可视为算法。本书只介绍比较有趣和有代表性的部分。

二分法查找

使用二分法查找时，每次与中间的数字做比较，从而将余下的数字排除一半。比如要在100（n）个元素中找到1。注意仅当列表是有序的情况下才可以用二分法。

不管找哪个数字，都能在7次内找到。而简单查找法的最坏情况是100（n）次，即挨个查找。

对数

对数是幂运算的逆运算。

$$\log_{10}100 \ 相当于问“将多少个10相乘的结果为100”$$

使用二分查找时，最多需要检查log n（本书log均以2为底，即 $log_{2}n$ ）个元素。如果列表包含8个元素，最多检查3个元素，这里的3就是来自 $\log 8 = 3 (2^3 = 8)$ 。

Python示例代码

二分法查找

def binary_search(list, item):
  # low and high keep track of which part of the list you'll search in.
  low = 0
  high = len(list) - 1

  # While you haven't narrowed it down to one element ...
  while low <= high:
    # ... check the middle element
    mid = (low + high) // 2
    guess = list[mid]
    # Found the item.
    if guess == item:
      return mid
    # The guess was too high.
    if guess > item:
      high = mid - 1
    # The guess was too low.
    else:
      low = mid + 1

  # Item doesn't exist
  return None

my_list = [1, 3, 5, 7, 9]
print(binary_search(my_list, 3)) # => 1

# 'None' means nil in Python. We use to indicate that the item wasn't found.
print(binary_search(my_list, -1)) # => None

运行时间

简单查找法的最多需要查找的次数与列表长度相同，这被称为线性时间（linear time）。二分查找的运行时间被称为对数时间（log time）。

大O表示法

大O表示法是一种特殊的表示法，计算的是操作数，指出了算法的速度有多快。算法的运行时间用大O表示法表示。大O表示法让你能够比较操作数，实质上它指出了算法运行时间的增速。

举一个例子，你要画一个包含16个格子的网格。

算法1

每次画一个小格子，画一个格子算一次操作，这样需要多少次操作？16次。

算法1

算法2

将纸不断的对折，折4次之后再打开，就可以得到16个格子。

算法2

上述两种算法如果用大O表示法表示，算法1的运行时间是O(n)，算法2的运行时间是O(log n)。

注意大O表示法说的是最糟情形。比如你在用简单查找法查找一个目标元素，而这个元素正好在序列的第一位，所以只需要一步便可以找到目标，而这你无法称其运行时间为O(1)。简单查找法的运行时间永远都是O(n)，这只是让你知道其运行时间不可能超过O(n)。

一些常见的大O运行时间

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

大O表示法	描述
O(log n)	也叫对数时间，这样的算法包括二分查找
O(n)	也叫线性时间，这样的算法包括简单查找
O(n * log n)	这样的算法包括后续要介绍的快速排序----一种速度较快的排序算法
O($n^2$ )	这样的算法包括后续介绍的选择排序----一种速度较慢的排序算法
O(n!)	也叫阶乘时间，这样的算法包括后续介绍的旅行商问题的解决方案----一种非常慢的算法

下面按从快到慢的顺序列出了使用这些常见运行时间的增速曲线。

重要

• 算法的速度指的并非时间，而是操作数的增速

• 算法运行时间是从其增速的角度度量的

• 谈论算法的速度时，我们说的是随着输入的增加，其运行时间将以什么样的速度增加。

• O(log n) 比O(n)快，当需要搜索的元素越多时，前者比后者快得越多。

旅行商问题

计算机科学领域有一个非常著名的旅行商问题，其计算时间增加得非常快，而且大家普遍认为没有改进空间。

5个城市的旅行商问题

有一个旅行商，他要前往5个城市，同时要确保旅程最短。为此，我们需要考虑前往这些城市的各种可能顺序。对于每种顺序，我们都需要计算总旅程，再挑选出旅程最短的路线，这样5个城市有120种不同的排列方式。

推而广之，涉及n个城市时，需要执行n!（n的阶乘）次操作才能计算出结果。因此运行时间为O(n!)，即阶乘时间。如果涉及的城市数超过100，根本就不能在合理的时间内计算出结果----等计算出来，太阳都没了。

对于这个问题，目前还没有找到更快的算法，我们能做到只是去找出近似答案。