网站建设对于企业的意义,移动app开发技术,色盲,温州市建设局网站whats the 算法 算法#xff08;Algorithm#xff09;是指解题方案的准确而完整的描述#xff0c;是一系列解决问题的清晰指令#xff0c;算法代表着用系统的方法描述解决问题的策略机制。也就是说#xff0c;能够对一定规范的输入#xff0c;在有限时间内获得所要求的输…whats the 算法 算法Algorithm是指解题方案的准确而完整的描述是一系列解决问题的清晰指令算法代表着用系统的方法描述解决问题的策略机制。也就是说能够对一定规范的输入在有限时间内获得所要求的输出。如果一个算法有缺陷或不适合于某个问题执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。 算法中的指令描述的是一个计算当其运行时能从一个初始状态和可能为空的初始输入开始经过一系列有限而清晰定义的状态最终产生输出并停止于一个终态。一个状态到另一个状态的转移不一定是确定的。随机化算法在内的一些算法包含了一些随机输入。 时间复杂度 时间复杂度用于评估算法运行效率。 在计算机科学中算法的时间复杂度是一个函数它定性描述了该算法的运行时间。这是一个关于代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述不包括这个函数的低阶项和首项系数。通常写法为O(n) 举例说明 print(Hello World) #O(1) 只执行一次for i in range(n): print(Hello World) #O(n) 执行了n次for i in range(n): for j in range(n): print(Hello World) #O(n**2) 执行了n*n次for i in range(n): for j in range(n): for k in range(n): print(Hello World) #O(n**3) 执行了n*n*n次while n 1: print(n) n n // 2n64时输出64
32
16
8
4
2 所以我们发现这个执行的次数是2的幂次方O(log2 n)简写为O(logn)注意时间复杂度没有O(3)、O(1/2n)、O(n^2n)的说法因为时间复杂度只是一个用于衡量的估算值所以上述改写为O(1)、O(n)、O(n^2)即可 一般来说时间复杂度高的算法比时间复杂度低的算法效率要慢常见的时间复杂度按效率排序为 O(1) O(logn) O(n) O(nlogn) O(n^2) O(n^2*logn) O(n^3) 当然还有一些不常用的时间复杂度——O(n!) O(2^n) O(n^n) …这些都不重要 空间复杂度 空间复杂度(Space Complexity)用来评估算法内存占用大小的一个式子。 空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度记做S(n)O(f(n))。比如直接插入排序的时间复杂度是O(n^2),空间复杂度是O(1) 。而一般的递归算法就要有O(n)的空间复杂度了因为每次递归都要存储返回信息。一个算法的优劣主要从算法的执行时间和所需要占用的存储空间两个方面衡量。 一般小程序的情况下我们通常会稍微牺牲点内存来加快效率即我们会用空间换时间所以我们会适当提高空间复杂度以减少时间复杂度。 列表查找 算法最基本的应用就是对列表的查找与排序这里我们说一下列表查找。 列表查找就是针对一个列表中待查找的元素输出该元素的索引值index如果该列表中不含有目标值则输出None 列表查找的方式有两种——顺序查找与二分查找 顺序查找从列表第一个元素开始顺序进行搜索直到找到为止。 二分查找从有序列表的候选区data[0:n]开始通过对待查找的值与候选区中间值的比较可以使候选区减少一半。 li[1,2,3,4,5,6,7,8,9,10]#顺序查找
def linear_search(data_set, value):for i in data_set:if data_set[i] value:return ireturnthe_indexlinear_search(li,3)
print(the_index)#2 O(n)#二分查找
def bin_search(data_set, value):low 0high len(data_set) - 1while low high:mid (lowhigh)//2if data_set[mid] value:return midelif data_set[mid] value:high mid - 1else:low mid 1bin_indexbin_search(li,3)
print(bin_index)#2 O(logn) 可以发现二分查找比顺序查找要更快 二分法可使用递归完善 def bin_search_rec(data_set,value,low,high):if low high:mid(lowhigh) // 2if data_set[mid] value:return midelif data_set[mid] value:return bin_search_rec(data_set,value,low,mid-1)else:return bin_search_rec(data_set,value,mid1,high)else:return Noneli[1,2,3,4,5,6,7,8,9,10]
abin_search_rec(li,3,1,10)
print(a)#2 使用递归的二分法 列表查找小练习 现有一个学员信息列表按id增序排列格式为 [ {id:1001, name:张三, age:20}, {id:1002, name:李四, age:25}, {id:1004, name:王五, age:23}, {id:1007, name:赵六, age:33} ] 修改二分查找代码输入学生id输出该学生在列表中的下标并输出完整学生信息。 列表排序 列表排序即将无需列表变为有序Python的内置函数为sort()。应用的场景主要有各种榜单、各种表格、给二分查找用、 其他算法用等等。 有关列表排序的算法有很多主要分为 low B三人组 冒泡排序、 选择排序、 插入排序 NB三人组 快速排序、 堆排序、 归并排序 其他排序算法 基数排序、 希尔排序、 桶排序 有关列表排序算法博客链接地址http://www.cnblogs.com/zhuminghui/p/8401129.html 转载于:https://www.cnblogs.com/zhuminghui/p/8400216.html
