what's the 算法
时间复杂度
时间复杂度用于评估算法运行效率。
在计算机科学中，算法的时间复杂度是一个函数，它定性描述了该算法的运行时间。这是一个关于代表算法输入值的字符串的长度的函数。时间复杂度常用大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 // 2"""n=64时输出：643216842 所以我们发现这个执行的次数是2的幂次方，O(log2 n)简写为O(logn)""" 注意：时间复杂度没有O(3)、O(1/2n)、O(n^2+n)的说法，因为时间复杂度只是一个用于衡量的估算值，所以上述改写为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 i returnthe_index=linear_search(li,3)print(the_index)#2 O(n)#二分查找def bin_search(data_set, value): low = 0 high = len(data_set) - 1 while low <= high: mid = (low+high)//2 if data_set[mid] == value: return mid elif data_set[mid] > value: high = mid - 1 else: low = mid + 1bin_index=bin_search(li,3)print(bin_index)#2 O(logn) 可以发现二分查找比顺序查找要更快
二分法可使用递归完善：
def bin_search_rec(data_set,value,low,high): if low <= high: mid=(low+high) // 2 if data_set[mid] == value: return mid elif data_set[mid] > value: return bin_search_rec(data_set,value,low,mid-1) else: return bin_search_rec(data_set,value,mid+1,high) else:return Noneli=[1,2,3,4,5,6,7,8,9,10]a=bin_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三人组： 快速排序、 堆排序、 归并排序
-
其他排序算法： 基数排序、 希尔排序、 桶排序
有关列表排序算法博客链接地址：