算法设计与分析.ppt

《算法设计与分析.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、算法设计与分析LuChaojun,SJTU2LuChaojun,SJTU22查找问题问题:在一个列表中查找某个值.defsearch(x,nums):#nums为一数值列表,x是一个数#如果找到,返回x在列表中的位置#否则返回-1Python本身就提供有关的功能:判断:xinnums求位置:nums.index(x)LuChaojun,SJTU3LuChaojun,SJTU33策略一:线性查找逐个检查列表中的数据.defsearch(x,nums):foriinrange(len(nums)):ifnums[i]==x:returnireturn–1特点:适合无序数据列表不

2、适合大数据量使列表有序后,线性查找算法可略加改进.(How?)LuChaojun,SJTU4LuChaojun,SJTU44策略二:两分查找猜数游戏:可取的策略?两分查找:每次查看有序列表的中点数据,根据情况接着查找较大一半或较小一半.defsearch(x,nums):low,high=0,len(nums)-1whilelow<=high:mid=(low+high)/2ifx==nums[mid]:returnmidelifx

3、算法解题所耗"步数"(时间).步数又与问题难度相关查找问题中,问题难度用数据量n衡量LuChaojun,SJTU5LuChaojun,SJTU6LuChaojun,SJTU66查找算法的比较策略一步数与n成正比称为线性时间算法策略二步数与log2n成正比称为对数时间算法猜数游戏中:若数的范围是1~1000000,则策略一:平均要猜50万次才能猜对最坏1百万次,最好1次策略二:最坏也只需猜20次递归定义两分查找算法的另一表述:算法binarySearch:在nums[low]~nums[high]中查找xmid=(low+high)/2iflow>highx不在nums中el

4、ifx

5、eturn1else:returnn*fact(n-1)LuChaojun,SJTU9递归查找算法两分查找的递归版本:defrecBinSearch(x,nums,low,high):iflow>high:return-1mid=(low+high)/2ifx==nums[mid]returnmidelifx

6、len(nums)-1)LuChaojun,SJTU10递归vs迭代递归算法设计容易易读效率略低迭代算法:用循环设计困难有的问题没有直观的迭代算法效率高排序问题给定数据列表,将其数据重新排列,形成一个有序的(递增)列表.回顾:Python列表类型提供了方法.sort()我们要学的是如何实现这个方法,而不是学会用现成的朴素策略:选择排序每次从剩下的数据中选择最小值输出.求列表中最小值的算法:参考前面的max算法.defselSort(nums):n=len(nums)forbottominrange(n-1):#求nums[bottom]..nums[n-1]间

7、的最小值mp=bottom#初始bottom为迄今最小foriinrange(bottom+1,n):#考虑其他值ifnums[i]