数据结构和算法-01

数据结构和算法
基于《算法图解》—Aditya Bhargava和《数据结构》—严蔚敏

**

算法图解：(基于Python)*

第1章—算法简介

1.1 引言
算法是一组完成任务的指令。

1.2 二分查找（binary_search）
二分查找是一种算法，其输入是一个有序列表（必须有序）。如果要查找的元素包含在列表中，二分查找返回其位置；否则返回null。
1.2.1 普通查找和二分查找
例子：猜数字游戏
简单查找每次只能排除一个数字；而使用二分查找时，猜测的是中间的数字，从而每次都将余下的数字排除一半。一般而言，对于包含n个元素的列表，使用二分查找最多需要log n (默认2为底)步，而简单查找最多需要n步。

#二分查找
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

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

**练习**
1.1 假设有一个包含128个名字的有序列表，你要使用二分查找在其中查找一个
名字，请问最多需要几步才能找到？
1.2 上面列表的长度翻倍后，最多需要几步？
(答案见下章)

1.3 大O表示法
大O表示法是一种特殊的表示法，指出了算法的速度有多快。
二分查找和简单查找的运行时间的增速不同：随着元素数量的增加，二分查找需要的额外时间并不多，而简单查找需要的额外时间却很多。
大O表示法指出了最糟糕情况下的运行时间。
一些常见的大O运行时间：

O(log n)，也叫对数时间，包括二分查找；
O(n)，也叫线性时间，包括简单查找；
O(n*log n)，包括快速排序；
O(n²)，包括选择排序；
O(n!)

启示：

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

——持续修改完善中…