算法简介：查找与算法运行时间

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

1. 二分查找与简单查找

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

def binary_search(list, item):
low = 0
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 
1
2
3
4
5
6
7
8
9
10
11
12
13

简单查找即将元素全部遍历。

1.1 运行时间

大O表示法：一种特殊的表示法，指出算法的速度有多块。
大O表示法指的并非以秒为单位的速度。大O表示法让你能够比较操作数，它指出了算法运行时间的增速。

假设有10亿个元素有序排列，需要查找其中的一个元素，没查找一个元素需要消耗1毫秒，则简单查找需要11天左右，二分查找需要30ms。

假设列表有n个元素。

• 简单查找需要查找每个元素，因此需要执行n次操作，使用大O表示法，这个运行时间为O(n)。
• 二分查找需要执行log n次操作，使用大O表示为O(log n)。

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

一些常见的大O运行时间：
O(log n)，对数时间，如二分查找
O(n)，线性时间，如简单查找
O(n*log n)，如快速排序
O(n^2)，如选择排序
O(n!)，如旅行商问题

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

2. 旅行商问题

有一位旅行商。他需要前往5个城市，同时需要确保旅途最短。为此，可考虑前往各个城市的各种可能顺序。
对于每种顺序，他都计算总旅程，再挑选出旅程最短的路径。

• 5个城市有120钟不同的排列方式。
• 涉及6个城市时，需要执行720次操作。
• 涉及7个城市时，需要执行5040次操作。
• 涉及n个城市时，需要执行n!(n的阶乘)次操作。因此运行时间为O(n!)，即阶乘时间。