ADA算法分析基礎(chǔ)－整體框架

1、2022-3-2212022-3-222Review 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 pattern2022-3-223How to describe an algor

2、ithm?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 value of n to m and the value of r to n. Step5 Go to Step2.Advantages: easy understan

3、dDisadvantages: exist inherent ambiguity2022-3-224How to describe an algorithm? (II)bFlow chartStartr = 0Input m and nr = m % nm = nn = routput nStopA flowchart is a method of expressing an algorithm by a collection of connected geometric shapes containing descriptions of the algorithms steps.Advant

4、ages: intuitiveDisadvantages: lack flexibility2022-3-225How to describe an algorithm? (III)bProgramming 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

5、 f(n) = (g(n) f(n) = 2n3+3n-5 = (n3)f(n) = 2n4+1 = (n3) ?( )( )limf ng nnc2022-3-2228Asymptotic Notation: f(n) = (g(n)nf(n)c2g(n)n0c1g(n)2022-3-2229Orders 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 is

6、bAll polynomials of the same degree k belong to the same class: aknk + ak-1nk-1 + + a0 (nk) bExponential functions an have different orders of growth for different as2022-3-2230Basic asymptotic complexity classesfactorialn!exponential2ncubicn3quadraticn2n-log-nn log nlinearnlogarithmiclog nconstant1

7、2022-3-2231Asymptotic 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-3-2232Asymptotic Notation Using the o-notation, we can concisely express the fo