做非法网站怎么判刑,口碑好的做网站,长沙网站建设方案,公司网站开发详细流程数据结构和算法 基于《算法图解》—Aditya Bhargava和《数据结构》—严蔚敏
**
算法图解#xff1a;(基于Python)* 第1章—算法简介
1.1 引言 算法是一组完成任务的指令。
1.2 二分查找#xff08;binary_search#xff09; 二分查找是一种算法#xff0c;其输入是一个…数据结构和算法 基于《算法图解》—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 0high len(list-1)while low high:mid (lowhigh)//2guess list[mid]if guess item:return midif guess item:high mid -1else:low mid 1return Nonemy_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)快当需要搜索的元素越多时前者比后者快得越多。
——持续修改完善中…
