个人网站免费域名,网络设计,wordpress设置分类,wordpress修改插件路径文章目录 1. 二分查找与简单查找1.1 运行时间 2. 旅行商问题 算法是一组完成任务的指令。任何代码片段都可以视为算法。
1. 二分查找与简单查找
二分查找是一种算法#xff0c;其输入是一个有序的元素列表#xff0c;如果要查找的元素包含在列表中#xff0c;二分查找返回… 文章目录 1. 二分查找与简单查找1.1 运行时间 2. 旅行商问题 算法是一组完成任务的指令。任何代码片段都可以视为算法。
1. 二分查找与简单查找
二分查找是一种算法其输入是一个有序的元素列表如果要查找的元素包含在列表中二分查找返回其位置否则返回NULL。二分查找每次都检查中间的元素。
def binary_search(list, item):
low 0
high len(list) - 1
while low highmid (low high)/2guess list[mid]if guess item:return midif guess item:high mid - 1else:low mid 1
return None 简单查找即将元素全部遍历。
1.1 运行时间
大O表示法一种特殊的表示法指出算法的速度有多块。 大O表示法指的并非以秒为单位的速度。大O表示法让你能够比较操作数它指出了算法运行时间的增速。 假设有10亿个元素有序排列需要查找其中的一个元素没查找一个元素需要消耗1毫秒则简单查找需要11天左右二分查找需要30ms。 假设列表有n个元素。
简单查找需要查找每个元素因此需要执行n次操作使用大O表示法这个运行时间为O(n)。二分查找需要执行log n次操作使用大O表示为O(log n)。
大O表示法指出了最糟情况下的运行时间。 一些常见的大O运行时间 O(log n)对数时间如二分查找 O(n)线性时间如简单查找 O(n*log n)如快速排序 O(n^2)如选择排序 O(n!)如旅行商问题 算法的速度指的并非时间而是操作数的增速。、谈论算法的速度时我们说的是随着输入的增加其运行时间将以什么样的速度增加。算法的运行时间用大O表示法表示。O(log n)比O(n)快当需要搜索的元素越多时前者比后者快的越多。
2. 旅行商问题
有一位旅行商。他需要前往5个城市同时需要确保旅途最短。为此可考虑前往各个城市的各种可能顺序。 对于每种顺序他都计算总旅程再挑选出旅程最短的路径。
5个城市有120钟不同的排列方式。涉及6个城市时需要执行720次操作。涉及7个城市时需要执行5040次操作。涉及n个城市时需要执行n!(n的阶乘)次操作。因此运行时间为O(n!)即阶乘时间。
