读《算法图解》

1 算法简介

1.1 二分查找

对于一堆有序的数据，想要从中找到目标数据的位置。

第一步，先从中间找个基准点，目标与基准进行比较。

第二步，基准大于目标，连基准在内都大于的那一些数据不参与后续比较。

第三步，基准小于目标，连基准在内都小于的那一些数据不参与后续比较。

在剩余数据中，重复以上步骤。

在速度上，二分查找可以在对数运算logan

得出，a为2，n为数据量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def binary_search(list,item):
	low = 0
	high = len(list) - 1
	while low <= high:
		mid = (low + high) // 2
        # Python2 mid = int((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(len(my_list))
print(binary_search(my_list,3))

1.2 大O表示法

算法速度是指操作数的增速，算法运行时间用大O表示法表示，大O表示法指出了最糟情况下的运行时间。

  1. O(logan)，也叫对数时间，包括有二分查找。
  2. O(n)，也叫线性时间，包括有简单查找。
  3. O(n*logan)，包括有快速排序。
  4. O(n2)，包括有选择排序。
  5. O(n!)，解决旅行商问题。

下面按从快到慢的顺序列出了使用这些算法绘制网格所需的时间：

常见运行时间