算法设计与分析

查找问题 问题: 在一个列表中查找某个值. def search(x, nums): # nums为一数值列表, x是一个数 # 否则返回-1 2 2

查找问题 Python本身就提供有关的功能 判断: x in nums 求位置: nums.index(x) def search(x, nums) try: return num.index(x) #如何实现？ except: return -1 3 3 3

策略一: 线性查找 逐个检查列表中的数据 def search(x, nums): for i in range(len(nums)): if nums[i] == x: return i return –1 4 4

策略一: 线性查找 特点: 适合无序数据列表 不适合大数据量 使列表有序后, 线性查找算法可略加改进 (How?) 5 5 5

策略二: 二分查找 猜数游戏: 可取的策略? 二分查找: 每次查看有序列表的中点数据, 根据情况接着查找较大一半或较小一半 def search(x, nums): low, high = 0, len(nums) - 1 while low <= high: mid = (low + high) / 2 if x == nums[mid]: return mid elif x < nums[mid]: high = mid - 1 else: low = mid + 1 return -1 6 6 6

算法的优劣比较 经验分析 抽象分析 根据电脑上的运行时间比较 环境变化会影响结果 分析算法解题所耗“步数”(时间) 步数越少越好 步数又与 问题难度/规模 相关 查找问题中, 问题难度用数据量n衡量

查找算法的比较 策略一 策略二 猜数游戏中: 若数的范围是1~1000000,则 步数与n成正比 称为线性时间算法 步数与log2 n成正比(如：16个元素的列表) 称为对数时间算法 猜数游戏中: 若数的范围是1~1000000,则 策略一: 平均要猜50万次才能猜对 最坏1百万次, 最好1次 策略二: 最坏也只需猜20次 8 8 8

查找算法的比较 策略一 策略二 步数与n成正比 称为线性时间算法 步数与log2 n成正比(如：16个元素的列表) 称为对数时间算法 List Size Halvings 1 2 4 8 3 16 9 9 9

递归定义 二分查找算法的另一表述: 大问题的子问题仍是同样形式的问题,故仍用解决大问题的算法来解决子问题 算法binarySearch:在nums[low]~nums[high]中查找x mid = (low + high) / 2 if low > high x 不在nums中 elif x < nums[mid] 在nums[low]~nums[mid-1]中查找x else 在nums[mid+1]~nums[high]中查找x 大问题的子问题仍是同样形式的问题,故仍用解决大问题的算法来解决子问题 10

递归定义的特征 递归定义完全是合法的,数学里有很多递归定义的对象. 如阶乘: 这不是循环定义，有”出口” 当n = 0; n != 1 , 当n = 0; n != n * (n – 1) ! , 否则 11

递归定义的特征 递归定义的特征 有奠基情形, 这种情形无需递归 每次递归都是针对较小情形 递归链最后终止于奠基情形 12

Python递归函数 例如: 计算阶乘的递归函数 def fact(n): if n == 0: return 1 else: return n * fact(n-1) 13

递归查找算法 二分查找的递归版本: def recBinSearch(x, nums, low, high): if low > high: return -1 mid = (low + high) / 2 if x == nums[mid] return mid elif x < nums[mid]: return recBinSearch(x, nums, low, mid-1) else: return recBinSearch(x, nums, mid+1, high) def search(x, nums): return recBinSearch(x, nums, 0, len(nums)-1) 14

递归 vs 迭代 递归算法 设计容易 易读 效率略低 迭代算法: 用循环 设计困难 有的问题没有直观的迭代算法 效率高

排序问题 给定数据列表, 将其数据重新排列, 形成一个有序的(递增)列表 回顾:Python列表类型提供了方法 <list>.sort() 我们要学的是如何实现这个方法

朴素策略: 选择排序 每次从剩下的数据中选择最小值输出 求列表中最小值的算法: 参考前面的max算法 大数据量时效率低 def selSort(nums): n = len(nums) for bottom in range(n-1): # 求nums[bottom]..nums[n-1]间的最小值 mp = bottom # 初始bottom为迄今最小 for i in range(bottom+1,n): # 考虑其他值 if nums[i] < nums[mp]: mp = i # 新的迄今最小值 nums[bottom], nums[mp] = nums[mp], nums[bottom] 大数据量时效率低

分而治之: 归并排序 数据分成两组或更多组 分别对各组排序 再把已有序的各组归并(merge)成完整有序列表

分而治之: 归并排序 归并: 比较两组各自的第一个数据, 小者输出, 由该组的下一个数据顶上来继续比较 当某组没有数据,则将另一组整个输出. def merge(lst1, lst2, lst3): while 当lst1和lst2两组都有数据: 输出两组第一个数据的较小者至lst3 更新该组的第一个数据 while 某组没有数据了: 将另一组剩余数据输出至lst3

分而治之: 归并排序(续) 问题: 如何对各组排序? 似乎可以利用递归: 对每一组再次应用分而治之的归并排序 因为满足递归的前提条件: 奠基情形:组中只有一个数据时无需递归; 每次分组都使列表变小, 最终会到达奠基情形

分而治之: 归并排序(续) 利用递归 def mergeSort(nums): n = len(nums) if n > 1: m = n / 2 nums1, nums2 = nums[:m], nums[m:] mergeSort(nums1) mergeSort(nums2) merge(nums1, nums2, nums)

排序算法的比较 难度和列表大小n有关 选择排序 每次循环: 从剩余数据中选择最小值, 所需步数为剩余数据的个数 总的步数: n+(n-1)+...+1 = n(n+1)/2 称为n2算法

排序算法的比较 难度和列表大小n有关 选择排序 (n2算法) 归并排序 作分组归并图示, 可知 每层归并都涉及n步(拷贝n个数据) 共有log2n层 故需nlog2n步, 称为nlogn算法

排序算法的比较 难度和列表大小n有关 选择排序 (n2算法) 归并排序 (nlogn算法)

可计算性与计算复杂性 问题可划分为: 可计算的: 存在确定的机械过程, 一步一步地解决问题 不可计算的: 不存在明确的机械过程来求解该问题 可计算, 而且能有效解决 可计算, 但难度太大, 不能有效解决 不可计算的: 不存在明确的机械过程来求解该问题 不可解, 不可判定

Hanoi塔问题 体现递归威力的经典问题! 三条规则 def moveTower(n, source, dest, temp): if n == 1: print "Move disk from", source, "to", dest+"." else: moveTower(n-1, source, temp, dest) moveTower(1, source, dest, temp) moveTower(n-1, temp, dest, source)

Hanoi塔问题 难度:需要2n − 1步! 称为指数时间算法 属于难解(intractable)问题. Number of Disks Steps in Solution 1 2 3 7 4 15 5 31

停机问题 能否编一个终止性判定程序HALT? 是不可解(unsolvable)问题! def HALT(prog,data) 若prog(data)终止, 则输出True; 否则输出False. 是不可解(unsolvable)问题!

停机问题 若有HALT, 则歌德巴赫猜想可以迎刃而解: def gc(): n = 2 while True: if 2*n 不是两个素数的和, 则返回False n = n + 1 然后运行HALT(gc)即可 哥德巴赫猜想主張每個大於等於4的偶數都是哥德巴赫數－可表示成兩個質數之和的數

停机问题(续) 说HALT不存在只能通过严格证明: 假设存在HALT(prog,data). 则编程序 def strange(p): result = HALT(p,p) if result == False: #即p(p)不终止 return else: while True: n = 1 运行strange(strange), 结果如何?

End 31