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

《算法与设计算法分析基础-整体框架.ppt》由会员分享，可在线阅读，更多相关《算法与设计算法分析基础-整体框架.ppt（33页珍藏版）》请在三一办公上搜索。

1、2023/10/17,2,2007-2008-01Design and Analysis of AlgorithmsSCUEC,Review of last class,How to solve a problem by computer,The notion of algorithm,Actual problemMathematics modelAlgorithm design and analysisProgrammingResult analysis,Input output finiteness effectiveness definiteness,Algorithm design p

2、attern,2023/10/17,3,2007-2008-01Design and Analysis of AlgorithmsSCUEC,How to describe an algorithm?,Natural 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;otherwise,proceed to Step 4.Step4 Assign t

3、he value of n to m and the value of r to n.Step5 Go to Step2.,Advantages:easy understand,Disadvantages:exist inherent ambiguity,2023/10/17,4,2007-2008-01Design and Analysis of AlgorithmsSCUEC,How to describe an algorithm?(II),Flow chart,A flowchart is a method of expressing an algorithm by a collect

4、ion of connected geometric shapes containing descriptions of the algorithms steps.,Advantages:intuitive,Disadvantages:lack flexibility,2023/10/17,5,2007-2008-01Design and Analysis of AlgorithmsSCUEC,How to describe an algorithm?(III),Programming language,Advantages:can run on computer directly,Disad

5、vantages: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)endl;,2023/10/17,6,2007-2008-01Design and Analysis of AlgorithmsSCUEC,How to describe an algorithm?(IV),Pseudocode,1 r=m%n;2 While r0 2.1 m=n;2.2 n=r;2.3 r=m%n;3 return n;

6、,Advantages:more precise than natural language,A pseudocode is a mixture of a natural language and programming language.It uses the basic grammar of programming language,but the operation instructions can designed with natural language.,Disadvantages:not exist a single form of pseudocode,Fundamental

7、s of the Analysis of Algorithm Efficiency(I),Chapter 2,1、The framework to analyze algorithms 2、Best,worst,average-case analysis 3、Three asymptotic notations,2023/10/17,8,2007-2008-01Design and Analysis of AlgorithmsSCUEC,Goals of this lecture,At the end of this lecture,you should be able toDescribe

8、how to analyze an algorithmUnderstand what is a best-case,worse-case and average-case analysisMaster the three asymptotic notations,O,rate of growth,2023/10/17,9,2007-2008-01Design and Analysis of AlgorithmsSCUEC,Analysis of algorithms,Definition:Algorithm analysis means to evaluate the two computer

9、 resources,time and space,which needed by an algorithm.Less resources an algorithm needs,more efficiency it is.Issues:time efficiencyDetermines the amount of time that algorithm needs to be executed.space efficiencyDetermines the amount of space that algorithm needs to be executed.Approaches:theoret

10、ical analysisempirical analysis,2023/10/17,10,2007-2008-01Design and Analysis of AlgorithmsSCUEC,Goal:Determines the amount of time that an algorithm needs to be executedMethods:Determines the exact amount of time that an algorithm needs to be executed Determines the number of repetitions of all the

11、 operations as a function of input size and input instanceWhere N is the input size,I is the input instance.,Theoretical analysis of time efficiency,2023/10/17,11,2007-2008-01Design and Analysis of AlgorithmsSCUEC,Operations,ComparisonsEqual,greater,not equal,Logical operationsAnd,or,xor,not,Arithme

12、tic operationsAdditions:add,subtract,increment,decrementMultiplications:multiply,divide,modAssignment operationX=1For convenience,each elementary operation is considered to use 1 time unit.,2023/10/17,12,2007-2008-01Design and Analysis of AlgorithmsSCUEC,Size of Input,Sorting and Finding problems:nu

13、mber of element in the array or tableGraph algorithms:number of vertices or edges,or sum of bothComputational Geometry:usually number of points,vertices,edges,line segments,or polygons.Matrix Operation:dimension of matrixNumber theory and cryptography:number of bits of input number,2023/10/17,13,200

14、7-2008-01Design and Analysis of AlgorithmsSCUEC,Examples,xx+1,for j1 to n do xx+1repeat,T(N,I)=3nn additions，2n assignments,T(N,I)=21 addition，1 assignment,for i1 to n do for j1 to n do xx+1 repeatrepeat,T(n)=3n2+nn2 additions，2n2+n assignments,2023/10/17,14,2007-2008-01Design and Analysis of Algori

15、thmsSCUEC,Theoretical analysis of time efficiency,Determining the number of repetitions of the basic operation as a function of input size and input instanceBasic operation:the operation that contributes most towards the running time of the algorithm T(N,I)copC(N,I),running time,execution timefor ba

16、sic operation,Number of times basic operation is executed,input size,input instance,2023/10/17,15,2007-2008-01Design and Analysis of AlgorithmsSCUEC,Input size and basic operation examples,2023/10/17,16,2007-2008-01Design and Analysis of AlgorithmsSCUEC,Best Case AnalysisLeast amount of work to be d

17、one over all of the possible input with the same sizeWorst Case Analysis(most important!)Most amount of work to be done over all of the possible input with the same size,Best-case,average-case,worst-case,2023/10/17,17,2007-2008-01Design and Analysis of AlgorithmsSCUEC,Average Case AnalysisThe amount

18、 of work averaged over all of the possible input sets with the same sizeNOT the average of worst and best case,Best-case,average-case,worst-case(II),2023/10/17,18,2007-2008-01Design and Analysis of AlgorithmsSCUEC,Example:Sequential search,Worst caseBest caseAverage case,2023/10/17,19,2007-2008-01De

19、sign and Analysis of AlgorithmsSCUEC,Rate of Growth(Important),The rate of growth of a function determines how fast the function value increases when the input increase,2023/10/17,20,2007-2008-01Design and Analysis of AlgorithmsSCUEC,Rate of Growth,The function x3 grows faster than the function x2If

20、 algorithm A does x3 operations on an input of size x and algorithm B does x2 operations,algorithm B is more efficientBecause of the relative rates of growth of functions,we will consider the functions x3+x2+x equivalent to x3(the reason is that when x is large,the difference between them is little,

21、so we only keep the item that grows fastest while omit others),2023/10/17,21,2007-2008-01Design and Analysis of AlgorithmsSCUEC,Classification of Growth,Big Omega(f):The class of functions that grow at least as fast as the function f,and maybe fasterBig Oh O(f):The class of functions that grow no fa

22、ster than f,and maybe slowerBig Theta(f)The class of functions that grow at the same rate as the function f,2023/10/17,22,2007-2008-01Design and Analysis of AlgorithmsSCUEC,Asymptotic Notation:O(most important!),O-notation:asymptotic upper boundCall f(n)=O(g(n)if there exist positive constants c and

23、 n0 such that 0 f(n)cg(n)for all n n0.Or,if,then f(n)=O(g(n)f(n)=2n3+3n-5=O(n3)f(n)=2n3+3n-5=O(n4)In the analysis literature,f(n)=O(g(n)means f(n)O(g(n)Thinking:2n=O(2n+1)?2n+1=O(2n)?(logn)2=O(n)?(n+1)!=O(n!),2023/10/17,23,2007-2008-01Design and Analysis of AlgorithmsSCUEC,Asymptotic Notation:O,n,f(

24、n),cg(n),n0,f(n)=O(g(n),2023/10/17,24,2007-2008-01Design and Analysis of AlgorithmsSCUEC,Asymptotic Notation:,-notation:asymptotic lower boundCall f(n)=(g(n)if there exist positive constants c and n0 such that 0 cg(n)f(n)for all n n0.or,if,then f(n)=(g(n)f(n)=2n3+3n-5=(n3)f(n)=2n3+3n-5=(n2)In the an

25、alysis literature,f(n)=(g(n)means f(n)(g(n),2023/10/17,25,2007-2008-01Design and Analysis of AlgorithmsSCUEC,Asymptotic Notation:,n,cg(n),f(n),n0,f(n)=(g(n),2023/10/17,26,2007-2008-01Design and Analysis of AlgorithmsSCUEC,Some properties of asymptotic order of growth,f(n)O(f(n)f(n)O(g(n)iff g(n)(f(n

26、)If f(n)O(g(n)and g(n)O(h(n),then f(n)O(h(n)If f1(n)O(g1(n)and f2(n)O(g2(n),then f1(n)+f2(n)O(maxg1(n),g2(n),2023/10/17,27,2007-2008-01Design and Analysis of AlgorithmsSCUEC,Asymptotic Notation:,-notation:Call f(n)=(g(n)if there exist positive constants c1,c2,and n0 such that 0 c1g(n)f(n)c2g(n)for a

27、ll n n0.or,if,c is a constant and c 0,then f(n)=(g(n)f(n)=2n3+3n-5=(n3)f(n)=2n4+1=(n3)?,2023/10/17,28,2007-2008-01Design and Analysis of AlgorithmsSCUEC,Asymptotic Notation:,f(n)=(g(n),n,f(n),c2g(n),n0,c1g(n),2023/10/17,29,2007-2008-01Design and Analysis of AlgorithmsSCUEC,Orders of growth of some i

28、mportant functions,All logarithmic functions loga n belong to the same class(log n)no matter what the logarithms base a 1 isAll polynomials of the same degree k belong to the same class:aknk+ak-1nk-1+a0(nk)Exponential functions an have different orders of growth for different as,2023/10/17,30,2007-2

29、008-01Design and Analysis of AlgorithmsSCUEC,Basic asymptotic complexity classes,2023/10/17,31,2007-2008-01Design and Analysis of AlgorithmsSCUEC,Asymptotic Notation:o,o-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+

30、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),2023/10/17,32,2007-2008-01Design and Analysis of AlgorithmsSCUEC,Asymptotic Notation,Using the o-notation,we can concisely express the following hierarchy of complexity classes.Polynomial complexity classes:11)n!nn,The End,