1、2022-7-2422007-2008-01Design and Analysis of AlgorithmsSCUECReview of last classbHow to solve a problem by computerbThe notion of algorithm Actual problem Mathematics model Algorithm design and analysis Programming Result analysis Input output finiteness effectiveness definitenessbAlgorithm design p
2、attern2022-7-2432007-2008-01Design and Analysis of AlgorithmsSCUECHow to describe an algorithm?bNatural language Step1 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;otherwise,proceed to Step 4.Step4 Assign the v
3、alue of n to m and the value of r to n.Step5 Go to Step2.Advantages:easy understandDisadvantages:exist inherent ambiguity2022-7-2442007-2008-01Design and Analysis of AlgorithmsSCUECHow to describe an algorithm?(II)bFlow chartStartr=0Input m and nr=m%nm=nn=routput nStopA flowchart is a method of expr
4、essing an algorithm by a collection of connected geometric shapes containing descriptions of the algorithms steps.Advantages:intuitiveDisadvantages:lack flexibility2022-7-2452007-2008-01Design and Analysis of AlgorithmsSCUECHow to describe an algorithm?(III)bProgramming languageAdvantages:can run on
5、 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)?()()limf ng nnc2022-7-24282007-2008-01Design and Analysis of AlgorithmsSCUECAsymptotic Notation:f
6、(n)=(g(n)nf(n)c2g(n)n0c1g(n)2022-7-24292007-2008-01Design and Analysis of AlgorithmsSCUECOrders 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 degree k belong to the same cla
7、ss:aknk+ak-1nk-1+a0 (nk)bExponential functions an have different orders of growth for different as2022-7-24302007-2008-01Design and Analysis of AlgorithmsSCUECBasic asymptotic complexity classesfactorialn!exponential2ncubicn3quadraticn2n-log-nn log nlinearnlogarithmiclog nconstant12022-7-24312007-20
8、08-01Design and Analysis of AlgorithmsSCUECAsymptotic Notation:obo-notation Call 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)means that nlogn=O(n2),but n2 O(nlogn)()()lim0f ng nn2022-7-24322007-2008-01Design and Analysis of AlgorithmsSCUECAsymptotic 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!nnThe End
