算法与设计算法分析基础－整体框架.ppt

《算法与设计算法分析基础－整体框架.ppt》由会员分享，可在线阅读，更多相关《算法与设计算法分析基础－整体框架.ppt（33页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、算法与设计算法分析基础整体框架 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望Review of last classbHow to solve a problem by computerbThe notion of algorithmActual problemMathematics modelAlgorithm design and analysisProgrammingResult analysisInput output finiteness effect

2、iveness definitenessbAlgorithm design pattern2022/12/622010-2011-01 Design and Analysis of Algorithm SCUECHow to describe an algorithm?bNatural languageStep1 Input m and n.Step2 Divide m by n and assign the value of the remainder to r.Step3 If r=0,return the value of n as the answer and stop;otherwi

3、se,proceed to Step 4.Step4 Assign the value of n to m and the value of r to n.Step5 Go to Step2.Advantages:easy understandDisadvantages:exist inherent ambiguity2022/12/632010-2011-01 Design and Analysis of Algorithm SCUECHow to describe an algorithm?(II)bFlow chartStartr=0Input m and nr=m%nm=nn=rout

4、put nStopA flowchart is a method of expressing an algorithm by a collection of connected geometric shapes containing descriptions of the algorithms steps.Advantages:intuitiveDisadvantages:lack flexibility2022/12/642010-2011-01 Design and Analysis of Algorithm SCUECHow to describe an algorithm?(III)b

5、Programming languageAdvantages:can run on computer directly Disadvantages:lack abstraction#include int GCD(int m,int n)int r=m%n;while(r!=0)m=n;n=r;r=m%n;return n;void main(void)cout GCD(60,24)0,then f(n)=(g(n)f(n)=2n3+3n-5=(n3)f(n)=2n4+1=(n3)?2022/12/6272010-2011-01 Design and Analysis of Algorithm

6、 SCUECAsymptotic Notation:f(n)=(g(n)nf(n)c2g(n)n0c1g(n)2022/12/6282010-2011-01 Design and Analysis of Algorithm SCUECOrders of growth of some important functionsbAll logarithmic functions loga n belong to the same class (log n)no matter what the logarithms base a 1 isbAll polynomials of the same deg

7、ree k belong to the same class:aknk+ak-1nk-1+a0 (nk)bExponential functions an have different orders of growth for different as2022/12/6292010-2011-01 Design and Analysis of Algorithm SCUECBasic asymptotic complexity classesfactorialn!exponential2ncubicn3quadraticn2n-log-nn log nlinearnlogarithmiclog

8、 nconstant12022/12/6302010-2011-01 Design and Analysis of Algorithm SCUECAsymptotic Notation:obo-notationCall f(n)=o(g(n)if there exist positive constants c and n0 such that f(n)cg(n)for all n n0.Or,if ,then f(n)=o(g(n)f(n)=2n3+3n-5=o(n4)f(n)=o(g(n)if and only if f(n)=O(g(n),but g(n)O(f(n)nlogn=o(n2

9、)means that nlogn=O(n2),but n2 O(nlogn)2022/12/6312010-2011-01 Design and Analysis of Algorithm SCUECAsymptotic Notation Using the o-notation,we can concisely express the following hierarchy of complexity classes.bPolynomial complexity classes:1 logn n nlogn n2 1)n!nn2022/12/6322010-2011-01 Design and Analysis of Algorithm SCUECThe End2022/12/6332010-2011-01 Design and Analysis of Algorithm SCUEC