算法设计与分析.ppt

算法设计与分析,排序问题,将数据集合中的数据按从小到大的顺序重新排列. 这是计算机科学中产生丰富算法的领域 插入,选择,冒泡,快速,归并,. Python列表类型提供了方法 .sort(),朴素策略:选择最小值,思想:每次从剩下的数据中选择最小值输出. 如何求一批数据的最小值? 逐个检查数据,记下当前最小值. 最小值输出 如果数据集合是列表,则第一次最小值放入0号单元,第二次最小值放入1号单元,选择排序算法,代码 def selSort(list): n = len(list) for i in range(n-1): # 求listilistn-1间的最小值 min = i # 初始i为当前最小 for j in range(i+1,n): # 与后面值比大小 if listj listmin: min = j # 新的当前最小值 listi,listmin = listmin,listi 大数据量时效率低.,分而治之策略,分治法:将难以处理的大问题分解为若干个较小的子问题,然后分别解决这些子问题,并从子问题的解构造出原问题的解. 子问题经常类似大问题,因此可利用递归法来设计算法.,归并排序算法,数据集S平分成两个子集S1和S2,分别对S1和S2排序,得到两个“局部有序“序列. 再将两个局部有序序列归并(merge)成“全局有序“的序列S3.,归并排序算法,归并排序算法,归并排序算法,局部有序序列的归并,归并:比较两组各自的第一个数据,小者输出,由该组的下一个数据顶上来继续比较. 当某组没有数据,则将另一组整个输出. def merge(list1,list2,mergelist): while 当list1和list2两组都有数据: 输出两组第一个数据的较小者至mergelist 更新该组的第一个数据 while 某组没有数据了: 将另一组剩余数据输出至mergelist,归并排序,问题:如何对S1和S2排序? 递归:对每一组再次应用分治法 奠基情形:组中只有一个数据时无需递归; 每次分组都使列表变小,最终会到达奠基情形. def mergeSort(datalist): n = len(datalist) if n 1: m = n / 2 list1,list2 = datalist:m,datalistm: mergeSort(list1) mergeSort(list2) merge(list1,list2,datalist),算法的优劣比较,对同一问题可设计多种算法,如何比较优劣? 正确性不是唯一标准 耗费的时间(和空间)很重要! 经验分析:比较电脑上实际运行时间 依赖于平台 算法分析:分析算法代码,估算解题所耗“步数“(时间). 步数越多,时间越长 平台无关,12,算法复杂度,算法复杂度与问题数据量(规模)有关 常用n表示问题规模 算法复杂度是n的函数 尤其关心当n越来越大时,算法复杂度会如何变化 def f1(): def f2(): def f(n): x=0 x=0 x=0 for i in range(10): for i in range(20) for i in range(n): x=x+1 x=x+1 x=x+1,大O表示法,根据函数的增长率特性来刻画函数 令f(n)和g(n)是两个函数,如果存在正常数c使得只要n足够大(例如n n0), 则记为,15,15,15,搜索算法的比较,线性搜索 步数与n成正比:O(n) 称为线性时间算法 二分搜索 步数与log2 n成正比:O(log2 n)或O(log n) 称为对数时间算法 猜数游戏中:若数的范围是11000000,则 线性策略:平均要猜50万次才能猜对 最坏1百万次,最好1次 二分搜索:最坏也只需猜20次,排序算法的比较,选择排序 每次循环:从剩余数据中选择最小值,所需步数为剩余数据的个数 步数: n+(n-1)+.+1 = n(n+1)/2 称为二次方时间算法:O(n2) 归并排序 每层归并都涉及n步 共有log2n层 nlog2n时间算法:O(nlogn),Hanoi塔算法,难度:需要2n 1步! 指数时间算法:O(2n) 根据Hanoi塔的传说:有64个金盘.就算僧侣1秒移动一次,至少也要花 2641秒,大约等于5850亿年.,各种复杂度的比较,如图,可计算性,问题可划分为: 可计算的:存在确定的机械过程,一步一步地解决问题. 可计算,而且能有效解决 可计算,但难度太大,不能有效解决 不可计算的:不存在明确的机械过程来求解该问题. 不可解,不可判定,停机问题,能否编一个终止性判定程序HALT? def HALT(prog,data) 若prog(data)终止,则输出True;否则输出False. 是不可解(unsolvable)问题! 若存在HALT,则歌德巴赫猜想可以迎刃而解: def gc():