算法与设计算法分析基础-整体框架.ppt
《算法与设计算法分析基础-整体框架.ppt》由会员分享,可在线阅读,更多相关《算法与设计算法分析基础-整体框架.ppt(33页珍藏版)》请在三一文库上搜索。
1、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 desig
2、n 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
3、 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
4、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
5、 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
6、=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
7、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 th
8、is 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: Al
9、gorithm 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
10、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 nee
11、ds 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,Compariso
12、ns 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-201
13、1-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 Operatio
14、n: 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
15、 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 operatio
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 算法 设计 分析 基础 整体 框架
链接地址:https://www.31doc.com/p-3227064.html