算法分析与设计课件.ppt

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

1、1TheRoleofAlgorithmsinComputing1whatarealgorithms?2whyisthestudyofalgorithmsworthwhile?3whatistheroleofalgorithms?Analgorithmissaidtobecorrectif,foreveryinputinstance,ithaltswiththecorrectoutputTheproblemofsortingInput:sequenceofnumbers.Output:permutation

2、>suchthata'1≤a'2≤…≤a'n.Example:解释什么是实例？Input:824936Output:234689TimeIsImportant“Timeisimportantforeverybody,especiallyforthecomputerscientistwhostudiesalgorithms.”J.S.YuWhatkindsofproblemsaresolvedbyalgorithms?LevelsofHardness1.Thereisnomethodtosolvetheprobleminfinitelymanysteps.2

3、.Theoretically,thereisanalgorithm,buttherunningtimeincreasestoomuchwiththesizeofinput,eventotheuniverseage（NPCproblems）.3.Amongthe"good"algorithms,thereisstillahierarchyofrunningtime.多项式算法：把渐近复杂性与规模N的幂同阶的这类算法称为多项式算法。指数型算法：把渐近复杂性与规模N的指数同阶的这类算法称为指数型算法。这两种算法在效率上有质的区别的内在原因是算法渐近复杂性的阶的区

4、别。可见，算法的渐近复杂性的阶对于算法的效率有着决定性的意义。多项式算法是有效的算法。很多问题都有多项式算法。但也有一些问题还未找到多项式算法，只找到指数型算法。Homework1.1-3,1.1-41.2AlgorithmsasatechnologySupposecomputerswereinfinitelyfastandcomputermemorywasfree.Wouldyouhaveanyreasontostudyalgorithms?Comparetherunningtimeofinsertsortandmergesort.Whystudyalg

5、orithmsandperformance?•Algorithmshelpustounderstandscalability.•Performanceoftendrawsthelinebetweenwhatisfeasibleandwhatisimpossible.•Algorithmicmathematicsprovidesalanguagefortalkingaboutprogrambehavior.•Performanceisthecurrencyofcomputing.•Thelessonsofprogramperformancegenerali

6、zetoothercomputingresources.•Speedisfun!2GettingStartedAnalysisofAlgorithmsInsertionSortMergeSortTheproblemofsortingInput:sequenceofnumbers.Output:permutationsuchthata'1≤a'2≤…≤a'n.Example:Input:824936Output:234689AnExample:InsertionSortInsertionSort(A,n)

7、{fori=2ton{key=A[i]j=i-1;while(j>0)and(A[j]>key){A[j+1]=A[j]j=j-1}A[j+1]=key}}AnExample:InsertionSortInsertionSort(A,n){fori=2ton{key=A[i]j=i-1;while(j>0)and(A[j]>key){A[j+1]=A[j]j=j-1}A[j+1]=key}}301040201234i=j=key=A[j]=A[j+1]=AnExample:InsertionSortInsertionSort

8、(A,n){fori=2ton{key=A[i]j=i-1;w