百度怎么自己做网站,安徽互联网前十名公司,做外国网站,深圳网站建设公司选全通网络文章目录二分查找数据算法函数代码调用函数大OOO表示法表示算法运行速度一些常见的大 OOO 运行时间启示#xff1a;二分查找
二分查找是一种算法#xff0c;其输入是一个有序的元素列表和要查找的元素。如果要查找的元素包含在列表中#xff0c;二分查找返回其位置#xf…
文章目录二分查找数据算法函数代码调用函数大OOO表示法表示算法运行速度一些常见的大 OOO 运行时间启示二分查找
二分查找是一种算法其输入是一个有序的元素列表和要查找的元素。如果要查找的元素包含在列表中二分查找返回其位置否则返回null。
数据
函数形参列表xlist要查找的值item查找范围的索引low ~ high要去的索引mid猜测的值guess
算法
跟踪要查找的列表部分——开始时为整个列表每次都检查中间的元素xlist[mid]如果猜的数字小了就相应地修改low,如果猜的数字大了就修改high猜对了返回mid否则列表xlist里没有要查找的值iem返回None
函数代码
def binsearch(xlist, y): #注意list不能直接做形参low 0high len(xlist) - 1while low high:mid (low high) / 2mid round(mid) #一定要取整guess xlist[mid]if guess y:return midif guess y:high mid - 1else:low mid 1return None调用函数
import sys
sys.path.append(rD:\python\code)
import binsearch
x list(range(10,110)) #创建顺序数字列表
index binsearch.binsearch(x, 100)
print(index)大OOO表示法表示算法运行速度
仅知道算法需要多长时间才能运行完毕还不够还需知道运行时间如何随列表增长而增加。这正是大OOO表示法的用武之地。 大OOO表示法括号里面指出了最糟情况下的运行时间。
一些常见的大 OOO 运行时间
O(logn)O(log n)O(logn)也叫对数时间这样的算法包括二分查找。 O(n)O(n)O(n)也叫线性时间这样的算法包括简单查找。 O(n∗logn)O(n * log n)O(n∗logn)这样的算法包括快速排序——一种速度较快的排序算法。 O(n2)O(n^2)O(n2)这样的算法包括选择排序——一种速度较慢的排序算法。 O(n!)O(n!)O(n!)这样的算法包括旅行商问题的解决方案——一种非常慢的算法 还有其他的运行时间但这5种是最常见的。 这里做了简化实际上并不能如此干净利索地将大OOO运行时间转换为操作数但就目前而言这种准确度足够了。
启示
算法的速度指的并非时间而是操作数的增速。谈论算法的速度时我们说的是随着输入的增加其运行时间将以什么样的速度增加。算法的运行时间用大O表示法表示。O(logn)O(log n)O(logn)比O(n)O(n)O(n)快当需要搜索的元素越多时前者比后者快得越多
