算法与设计算法分析基础-整体框架.ppt
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 pattern,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 the 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 collection 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,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)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;,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,Fundamentals 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 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 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:theoretical 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 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,Arithmetic 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:number 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,2007-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 AlgorithmsSCUEC,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 basic 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 done 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 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-01Design 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 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,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 faster 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 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(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 analysis 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)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 all 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 important 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-2008-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+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,
