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

2019/8/2,2,2010-2011-01 Design and Analysis of Algorithm SCUEC,Review of last class,How to solve a problem by computer,The notion of algorithm,Actual problem Mathematics model Algorithm design and analysis Programming Result analysis,Input output finiteness effectiveness definiteness,Algorithm design pattern,2019/8/2,3,2010-2011-01 Design and Analysis of Algorithm SCUEC,How to describe an algorithm?,Natural 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 understand,Disadvantages: exist inherent ambiguity,2019/8/2,4,2010-2011-01 Design and Analysis of Algorithm SCUEC,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,2019/8/2,5,2010-2011-01 Design and Analysis of Algorithm SCUEC,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; ,2019/8/2,6,2010-2011-01 Design and Analysis of Algorithm SCUEC,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,2019/8/2,8,2010-2011-01 Design and Analysis of Algorithm SCUEC,Goals of this lecture,At the end of this lecture, you should be able to Describe how to analyze an algorithm Understand what is a best-case, worse-case and average-case analysis Master the three asymptotic notations , , O, rate of growth,2019/8/2,9,2010-2011-01 Design and Analysis of Algorithm SCUEC,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 efficiency Determines the amount of time that algorithm needs to be executed. space efficiency Determines the amount of space that algorithm needs to be executed. Approaches: theoretical analysis empirical analysis,2019/8/2,10,2010-2011-01 Design and Analysis of Algorithm SCUEC,Goal: Determines the amount of time that an algorithm needs to be executed Methods: 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 instance Where N is the input size, I is the input instance.,Theoretical analysis of time efficiency,2019/8/2,11,2010-2011-01 Design and Analysis of Algorithm SCUEC,Operations,Comparisons Equal, greater, not equal, Logical operations And, or, xor, not, Arithmetic operations Additions: add, subtract, increment, decrement Multiplications: multiply, divide, mod Assignment operation X = 1 For convenience, each elementary operation is considered to use 1 time unit.,2019/8/2,12,2010-2011-01 Design and Analysis of Algorithm SCUEC,Size of Input,Sorting and Finding problems: number of element in the array or table Graph algorithms: number of vertices or edges, or sum of both Computational Geometry: usually number of points, vertices, edges, line segments, or polygons. Matrix Operation: dimension of matrix Number theory and cryptography: number of bits of input number,2019/8/2,13,2010-2011-01 Design and Analysis of Algorithm SCUEC,Examples,xx+1,for j1 to n do xx+1 repeat,T(N,I) = 3n n additions，2n assignments,T(N,I) = 2 1 addition， 1 assignment,for i1 to n do for j1 to n do xx+1 repeat repeat,T(n) = 3n2+n n2 additions，2n2+n assignments,2019/8/2,14,2010-2011-01 Design and Analysis of Algorithm SCUEC,Theoretical analysis of time efficiency,Determining the number of repetitions of the basic operation as a function of input size and input instance Basic operation: the operation that contributes most towards the running time of the algorithm T(N,I) copC(N,I),running time,execution time for basic operation,Number of times basic operation is executed,input size, input instance,2019/8/2,15,2010-2011-01 Design and Analysis of Algorithm SCUEC,Input size and basic operation examples,2019/8/2,16,2010-2011-01 Design and Analysis of Algorithm SCUEC,Best Case Analysis Least amount of work to be done over all of the possible input with the same size Worst 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,2019/8/2,17,2010-2011-01 Design and Analysis of Algorithm SCUEC,Average Case Analysis The amount of work averaged over all of the possible input sets with the same size NOT the average of worst and best case,Best-case, average-case, worst-case (II),2019/8/2,18,2010-2011-01 Design and Analysis of Algorithm SCUEC,Example: Sequential search,Worst case Best case Average case,2019/8/2,19,2010-2011-01 Design and Analysis of Algorithm SCUEC,Rate of Growth (Important),The rate of growth of a function determines how fast the function value increases when the input increase,2019/8/2,20,2010-2011-01 Design and Analysis of Algorithm SCUEC,Rate of Growth,The function x3 grows faster than the function x2 If algorithm A does x3 operations on an input of size x and algorithm B does x2 operations, algorithm B is more efficient Because 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),2019/8/2,21,2010-2011-01 Design and Analysis of Algorithm SCUEC,Classification of Growth,Big Omega (f): The class of functions that grow at least as fast as the function f, and maybe faster Big Oh O(f): The class of functions that grow no faster than f, and maybe slower Big Theta (f) The class of functions that grow at the same rate as the function f,2019/8/2,22,2010-2011-01 Design and Analysis of Algorithm SCUEC,Asymptotic Notation: O (most important!),O-notation: asymptotic upper bound Call 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!),2019/8/2,23,2010-2011-01 Design and Analysis of Algorithm SCUEC,Asymptotic Notation: O,n,f(n),cg(n),n0,f(n) = O(g(n),2019/8/2,24,2010-2011-01 Design and Analysis of Algorithm SCUEC,Asymptotic Notation: ,-notation: asymptotic lower bound Call 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),2019/8/2,25,2010-2011-01 Design and Analysis of Algorithm SCUEC,Asymptotic Notation: ,n,cg(n),f(n),n0,f(n) = (g(n),2019/8/2,26,2010-2011-01 Design and Analysis of Algorithm SCUEC,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),2019/8/2,27,2010-2011-01 Design and Analysis of Algorithm SCUEC,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) ?,2019/8/2,28,2010-2011-01 Design and Analysis of Algorithm SCUEC,Asymptotic Notation: ,f(n) = (g(n),n,f(n),c2g(n),n0,c1g(n),2019/8/2,29,2010-2011-01 Design and Analysis of Algorithm SCUEC,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 is All 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,2019/8/2,30,2010-2011-01 Design and Analysis of Algorithm SCUEC,Basic asymptotic complexity classes,2019/8/2,31,2010-2011-01 Design and Analysis of Algorithm SCUEC,Asymptotic Notation: o,o-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),2019/8/2,32,2010-2011-01 Design and Analysis of Algorithm SCUEC,Asymptotic Notation,Using the o-notation, we can concisely express the following hierarchy of complexity classes. Polynomial complexity classes: 11) n! nn,The End,