本章内容
- 编写第一种查找算法:二分查找
- 学习如何谈论算法的运行时间:大O表示法
- 了解一种常用的设计方法:递归
什么是算法?
- 算法是一组完成任务的指令,任何代码片段都可以视为算法。
二分查找
- 二分查找是一种算法,其输入是一个有序的元素列表(仅当列表有序的时候,二分查找才管用)。如果要查找的元素包含在列表中,二分查找返回其位置,否则返回null。
首先介绍简单查找
简单查找就是‘傻找’,例如猜测一个1~100的数字,从1开始依次往上猜,每次猜测只能排除一个数字。如果数字是99,则需要猜测99次才能猜到。
二分查找
- 而二分查找法则从50开始,一下子可以排除一半的数字;每次都猜测中间的数字,从而每次都将剩余的数字排除一半。
-
一般而言,对于包含n个元素的列表,用二分查找最多需要[latex]\log n[/latex]步,而简单查找最多需要n步。
二分查找Python代码实现
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 #没有猜测的值
list = [1, 2, 3, 4, 5, 6, 7]
# 能找到对应的值
print(binary_search(list, 3))
print(binary_search(list, 6))
# 不能找到对应的值
print(binary_search(list, 8))
leetcode中的二分查找
运行时间
- 线性时间(linear time):以简单查找为例,最多的猜测次数与列表长度相同,这被称为线性时间-O(n)。
- 对数时间(log时间)::比如二分查找-O(log n).
线性时间和对数时间的增速不同!
大O表示法
大O表示法是一种特殊的表示法,指出了算法的速度有多快,同时也表示了算法的增速的差异,其单位并不是秒,而是操作数,指出了最糟糕情况下的运行时间。
一些常见的大O运行时间
从快到慢:
O(log n) 对数时间,如二分查找
O(n) 线性时间,如简单查找
O(n * log n ) 线性对数时间,如快速排序
O([latex]n^{2}[/latex]) 平方时间,如选择排序
O(n!) 阶乘时间,如旅行商问题
小结
- 算法的速度指的并非时间,而是操作数的增速
- 谈论算法的速度时,我们说的是随着输入的增加,其运行时间将以什么样的速度增加。
- 算法的运行时间用大O表示法表示
- O(log n)比O(n)快,当需要搜索的元素越多时,前者比后者快的越多。
发表回复