算法导论-第一章-导论PPT课件

.,1,Ch1导论,.,2,Alogrithm算法,Awell-definedcomputationalprocedurethattakessomevalue,orsetofvalues,asinputandproducessomevalue,orsetofvalues,asoutput.（良定义的计算过程，良定义指的是满足五个要素:有穷性、确定性、可行性、有输入和输出，计算过程指的是一系列的计算步骤）,Algorithm,Note：实例-计算一个解（输出）所有的输入,.,3,Applicationofalgorithm,人类基因组计划互联网路由问题：寻找数据由源节点到达目的节点的路径搜索问题制造业电子商务,.,4,Theproblemofsorting,Input:sequenceofnnaturalnumbersOutput:permutationsuchthata1a2an（重新排列）,Example-Input:-Output:,.,5,Exampleofinsertionsort,.,6,Exampleofinsertionsort,.,7,Insertionsort,.,8,Analysisofalgorithm算法分析-估计算法所需要的资源,Analysisanalgorithm:predictingtheresources,includingmemory,communicationbandwidth,orcomputerhardwareandsoon,thatthealgorithmrequires,Butmostoftenwewanttomeasurethecomputationaltimeofanalgorithm计算时间,Beforewecananalyzeanalgorithm,wemusthaveamodeloftheimplementationtechnologythatwillbeused,includingamodelfortheresourcesofthattechnologyandtheircosts计算模型,.,9,Weshallassumeagenericone-processor,random-accessmachine(RAM)modelofcomputation随机存储器作为计算模型指令一条接一条执行，没有并发操作指令作为一个原子操作被执行，指令包括算术操作、逻辑操作、数据移动和控制操作指令需要一个定量的执行时间RAM容量足够大,UnderRAMmodel:countfundamentaloperations计算基本操作数目,Analysisofalgorithm算法分析-估计算法所需要的资源,.,10,RAMmodel(RAM模型),为了在RAM模型上分析算法，我需要：Combinatorics组合Probabilitytheory概率Algebra代数Theabilitytoidentifythemostsignificanttermsinaformula找出最重要项的能力,.,11,Mainfactimpactingonrunningtime(影响运行时间的主要因素),Numbersofinputs输入规模Thedistributionofinput,some(notall)algorithmscantakedifferentamountsoftimetosorttwodifferentinputsequenceofthesamesize输入构成Usuallydescribetherunningtimeofaprogramasafunctionoftheinputsize通常将运行时间表示为输入的函数,.,12,Mainfactimpactingonrunningtime(影响运行时间的主要因素),Therunningtimeofanalgorithmmaydependingonhowthealgorithmisimplementedaswellaswhatkindofdatastructureisused有时候运行时间和算法采用的数据结构有关系Generally,weseekupperboundsontherunningtime,becauseeverybodylikesaguarantee,.,13,Inputsize(输入规模),输入规模依赖所研究的问题对许多计算问题，其输入规模就是输入项的个数，例如排序和计算傅里叶变换(DFT)，输入数组的元素个数n即为输入规模(Inputsize)对另外一些问题，例如两个整数相乘，其输入规模是输入在二进制表示下的位数有时候用二个数来表示输入，例如输入是一个图,因此需要确定每个问题的输入规模,.,14,Runningtime(运行时间),运行时间是指执行的基本操作数（步数），基本操作独立于具体机器假设每行代码花费的时间是常量Ci，但每一行代码花费的时间可能不同,.,15,Runningtime(运行时间),Worst-case:(usually)-T(n)=maximumtimeofalgorithmonanyinputofsizen.最坏情况下的运行时间，指的是size给定，任何输入实例的最长运行时间,Average-case:(sometimes)-T(n)=expectedtimeofalgorithmoverallinputsofsizen.-Needassumptionofstatisticsdistributionofinputs.平均情况下的运行时间，指的是size给定，不同的实例分布的平均所需的运行时间,Best-case:(bogus)-Cheatwithaslowalgorithmthatworksfastonsomeinput.最好情况下的运行时间，指的是size给定，输入实例的最短运行时间,.,16,Runningtime(运行时间),Theaveragerunningtimeisusuallyveryhardtocompute,weusuallystrivetoanalyzetheworstcaserunningtime.Theaveragecaseisoftenroughlyasbadastheworstcase平均情况难以分析，经常分析最坏情况Forsomealgorithms,worst-caseoccurfairlyoften最坏情况经常发生比如在数据库中寻找一条信息，若该信息不在数据库中，则搜索算法的最坏情况发生！Theworstcaserunningtimeisanupperboundontherunningtimeforanyinput,itisusuallyfairlyeasytoanalyzeandoftenclosetotheaverageorrealrunningtime最坏情况是上界,.,17,tj:thenumberoftimesthewhilelooptestinline5isexecutedforthejvalue第5行中while循环所做的测试次数,costtimes,c1,n,c2,n-1,0,n-1,c4,n-1,c5,c6,c7,c8,n-1,Analysisofinsertionsort,.,18,TocomputeT(n),therunningtimeofInsertion-sort,wesumtheproductsofthecostandtimescolumns,obtaining,Thebest-caseifthearrayisalreadysorted最好情况是数组已经有序tj=1,-Therunningtimeisalinearfunctionofn线性函数,Analysisofinsertionsort,.,19,Theworst-caseresultsifthearrayisinreversesortedorder-thatis,indecreasingorder最坏情况是数组是逆序tj=j,Therunningtimeisaquadraticfunctionofn二次函数,Analysisofinsertionsort,.,20,Analysisofinsertionsort,Theaverage-case:与输入的概率分布有关，假设对所有的数据出现的概率相等，tj=(j+1)/2,Therunningtimeisaquadraticfunctionofn二次函数,.,21,Orderofgrowth增长率,在算法分析过程中，通过抽象来简化分析过程，忽略每个语句的实际开销，代之以抽象的尝试Ci,“AsymptoticAnalysis”（渐进分析）,Ignorenotonlytheactualstatementcosts,butalsotheabstractcostsCi(usingtheconstantsa,b,andc是Ci的函数),对运行时间的增长率（速度）感兴趣，只考虑运行时间表达式中的最高次数项）（例如an2）,忽略首次项的系数，例如插入排序的最坏情况运行时间（又称为最坏情况时间复杂度）为(n2),.,22,Orderofgrowth增长率,.,23,Orderofgrowth增长率,几个常见运行时间增长率,.,24,-notation,Math:(g(n)=f(n):Thereexistpositiveconstantsc1,c2,andn00suchthat0c1g(n)f(n)c2g(n)forallnn0,Engine