《《算法设计与分析》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《算法设计与分析》PPT课件.ppt（22页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、算法设计与分析算法设计与分析排序问题排序问题将数据集合中的数据按从小到大的顺序将数据集合中的数据按从小到大的顺序重新排列重新排列.这是计算机科学中产生丰富算法的领域这是计算机科学中产生丰富算法的领域插入插入,选择选择,冒泡冒泡,快速快速,归并归并,.Python列表类型提供了方法列表类型提供了方法.sort()朴素策略朴素策略:选择最小值选择最小值思想思想:每次从剩下的数据中选择最小值输每次从剩下的数据中选择最小值输出出.如何求一批数据的最小值如何求一批数据的最小值?逐个检查数据逐个检查数据,记下当前最小值记下当前最小值.最小值输出最小值输出如果数据集合是列表如果数据集合是列表,则第一次最小值
2、放入则第一次最小值放入0号单号单元元,第二次最小值放入第二次最小值放入1号单元号单元,.选择排序算法选择排序算法代码代码def selSort(list):n=len(list)for i in range(n-1):#求求listi.listn-1间的最小值间的最小值 min=i#初始初始i为当前最小为当前最小 for j in range(i+1,n):#与后面值比大小与后面值比大小 if listj 1:m=n/2 list1,list2=datalist:m,datalistm:mergeSort(list1)mergeSort(list2)merge(list1,list2,data
3、list)算法的优劣比较算法的优劣比较对同一问题可设计多种算法对同一问题可设计多种算法,如何比较优劣如何比较优劣?正确性不是唯一标准正确性不是唯一标准耗费的时间耗费的时间(和空间和空间)很重要很重要!经验分析经验分析:比较电脑上实际运行时间比较电脑上实际运行时间依赖于平台依赖于平台算法分析算法分析:分析算法代码分析算法代码,估算解题所耗估算解题所耗步数步数(时间时间).步数越多步数越多,时间越长时间越长平台无关平台无关12算法复杂度算法复杂度算法复杂度与问题数据量算法复杂度与问题数据量(规模规模)有关有关常用常用n表示问题规模表示问题规模算法复杂度是算法复杂度是n的函数的函数尤其关心当尤其关心
4、当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),则记为则记为151515搜索算法的比较搜索算法的比较线性搜索线性搜索步数与步数与n成正比成正比:O(n)称
5、为线性时间算法称为线性时间算法二分搜索二分搜索步数与步数与log2 n成正比成正比:O(log2 n)或或O(log n)称为对数时间算法称为对数时间算法猜数游戏中猜数游戏中:若数的范围是若数的范围是11000000,则则线性策略线性策略:平均要猜平均要猜50万次才能猜对万次才能猜对最坏最坏1百万次百万次,最好最好1次次二分搜索二分搜索:最坏也只需猜最坏也只需猜20次次排序算法的比较排序算法的比较选择排序选择排序每次循环每次循环:从剩余数据中选择最小值从剩余数据中选择最小值,所需步所需步数为剩余数据的个数数为剩余数据的个数步数步数:n+(n-1)+.+1=n(n+1)/2称为二次方时间算法称为
6、二次方时间算法:O(n2)归并排序归并排序每层归并都涉及每层归并都涉及n步步共有共有log2n层层nlog2n时间算法时间算法:O(nlogn)Hanoi塔算法塔算法难度难度:需要需要2n 1步步!指数时间算法指数时间算法:O(2n)根据根据Hanoi塔的传说塔的传说:有有64个金盘个金盘.就算僧侣就算僧侣1秒移动一次秒移动一次,至少也要花至少也要花 2641秒秒,大约等于大约等于5850亿年亿年.各种复杂度的比较各种复杂度的比较如图如图可计算性可计算性问题可划分为问题可划分为:可计算的可计算的:存在确定的机械过程存在确定的机械过程,一步一步地一步一步地解决问题解决问题.可计算可计算,而且能有
7、效解决而且能有效解决可计算可计算,但难度太大但难度太大,不能有效解决不能有效解决不可计算的不可计算的:不存在明确的机械过程来求解不存在明确的机械过程来求解该问题该问题.不可解不可解,不可判定不可判定停机问题停机问题能否编一个终止性判定程序能否编一个终止性判定程序HALT?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=True:#即即p(p)终止终止 while True:pass else:return运行运行strange(strange),结果如何结果如何?2222End