分而治之(divide and conquer,D&C)
欧几里得算法
1 def gcd(a, b): 2 if a < b: 3 a, b = b, a 4 while b != 0: 5 a,b = b,a%b 6 return a
二分查找算法
1 #递归写法 2 def find(lit): 3 a=3 4 if len(lit) == 2: 5 print('最后找到') if a==lit[0] or a==lit[1] else print("没找到") 6 else: 7 num = len(lit)//2 8 if a>lit[num]: 9 find(lit[num + 1:]) 10 elif a<lit[num]: 11 find(lit[:num-1]) 12 else: 13 print('中间找到') 14 15 find([1,2,3,45,62,77,89,94,101,116,123,134])
4.2快速排序
-
4.2.1选择基准值,进行分区:
-
一个小于基准值数字组成的子数组
-
基准值
-
一个大于基准值的数组组成的子数组
归纳证明
快速排序算法
1 def(): 2 if len(array) < 2: 3 return array 4 else: 5 pivot = array[0] 6 less = [array[i] for i in range(len(array)) if array[i] < pivot] 7 greater = [array[i] for i in range(len(array)) if array[i] > pivot] 8 return quicksort(less) + [pivot] +quicksort(greater) 9 print(quicksort([1,5,4,8,6,3,28,])
4.3再讨论大O算法
-
4.3.1比较合并排序和快速排序
例1:简单的遍历一个列表
1 def print_items1(list): 2 for item in list: 3 print(item)
例2:遍历列表时休眠一秒
1 from time import sleep 2 def print_items2(list): 3 for item in list: 4 sleep(1) 5 print(item)
例1与例2的运行时间都是O(n).虽然使用大O表示法时,两种方法速度相同,但实际上例1速度更快.在O表示法O(n)中,n实际上是"c*n".c是算法所需固定时间量,被称为常量.通常不考虑,因为两种算法大O运行时间不同时,计算数很大时c变得无关紧要.
但对于快速查找和合并查找运行时间都为O(nlogn),而快速查找速度更快.快速查找相对于遇上最糟糕的情况,它遇上平均情况可能性更大.
-
4.3.2平均情况与最坏情况
快速排序算法并不会检测输入数组是否有序,因此其依然会对输入进行排序.如果每次都是将第一个作为基准值,调用栈的高度为O(n),若是以中间为基准值,高度为O(logn).无论基准值取值划分方式不同但调用栈中每一层都涉及O(n)个元素.因此最佳情况下整个算法所需时间为O(n)*O(logn)=O(nlogn),最坏情况下为O(n²)
注:快速排序中平均情况就是最佳情况.只要每次都随机选择基准值,平均运行时间就为O(nlogn).
-
小结
-
D&C将问题逐步分解处理列表时,基线条件很可能就是空数组或只包含一个元素的数组
-
实现快速排序时,随机选择基准值元素.可达到最佳情况.
-
大O表示法中的常量有时影响较大,注意比较分析.(快速排序与合并排序) (简单查找与二分查找)