数据结构课件_01Algorithms.pdf
数据结构课件_01Algorithms.pdf
Data Structures Algorithms Teacher : Wang Wei 1. Ellis Horowitz,etc., Fundamentals of Data Structures in C++ 2. 金远平, 数据结构 3. http://inside.mines.edu/~dmehta/ 4. 殷人昆, 数据结构 王伟, 计算机工程系, 东南大学 1 Why need algorithms • To computer science – The concept of an algorithm is fundamental • In developing large-scale computer systems – Algorithms • exist for many common problems • designing efficient algorithms plays a crucial role 王伟, 计算机工程系, 东南大学 2 Algorithm Definition • is a step-by-step procedure – a finite set of instructions to be executed in a certain order to get the desired output – • • if followed, accomplishes a particular task Algorithms are generally created independent of underlying languages 王伟, 计算机工程系, 东南大学 3 1 Characteristics Input Zero or more quantities are externally supplied Output At least one quantity is produced Definiteness Each instructions is clear abs unambiguous Finiteness If we trace out the instructions of an algorithm, then for all cases, the algorithm terminates after a finite number of steps Effectiveness Every instruction must be basic enough to be carried out 王伟, 计算机工程系, 东南大学 4 Algorithm Analysis and Measurement • Performance Criteria • Posteriori testing • Priori estimates – Asymptotic Analysis 王伟, 计算机工程系, 东南大学 5 Important Criteria • • • • • • Correctness Readability Efficiency Robustness Usability Simplicity 王伟, 计算机工程系, 东南大学 6 2 Complexities • Time Complexity of a program – is the amount of computer time it needs to run to completion • Running time or the execution time of operations of data structure must be as small as possible • Space Complexity of a program – is the amount of memory it needs to run to completion • Memory usage of a data structure operation should be as little as possible 王伟, 计算机工程系, 东南大学 7 Performance Measurement for Time Complexity • Posteriori testing – is concerned with obtaining the actual space and time requirements of a program 王伟, 计算机工程系, 东南大学 8 Example : Sequential Search int seqsearch ( int a[ ], int n, int x ) { //在a[0],…,a[n-1]中搜索与给定值 x 相等的元 //素，函数返回其位置，失败返回-1。 int i = 0; while ( i < n && a[i] != x ) i++; if ( i == n ) return -1; return i; } 王伟, 计算机工程系, 东南大学 9 3 Measuring the computing time of a program function time() or clock() • Example: double runTime; double start, stop; time(&start); int k = seqsearch (a, n, x); time(&stop); runTime = stop - start; cout << " RunTime : " << runTime << endl; 王伟, 计算机工程系, 东南大学 10 • These quantities are dependent on the particular compiler and options used as well as on the specific computer on which the program is run 王伟, 计算机工程系, 东南大学 11 Performance analysis for Time Complexity • Priori estimates ： – – to predict the growth in run time as the instance characteristics change asymptotic notation • Big “oh” : O 王伟, 计算机工程系, 东南大学 12 4 Asymptotic Notation • f (n) = O(g(n)) – iff (if and only if) there exist positive constants c and n0 such that f(n)≤cg(n) for all n, n≥n0 • g(n) – is an upper bound on the value – should be as small a function of n as one come up 王伟, 计算机工程系, 东南大学 13 Theorem 1.2 • if f(n) = amnm+…+ a1n+a0 , then f(n)=O(nm) – Proof : ∑ ∑ | | ∑ | |, – So, f(n) = O(nm) – When the complexity of an algorithm is actually, say, O(log n), – but we can only show that it is O(n) due to the limitation of our knowledge – it is OK to say so. – This is one benefit of O notation as upper bound. 王伟, 计算机工程系, 东南大学 14 How the various functions grow with n? Ultimate Laptop, 1 year 1 second 1E+60 1E+55 1E+50 2^N 1.2^N N^5 N^3 5N 1E+45 1E+40 1000 MIPS, since Big Bang 1E+35 1E+30 1E+25 1E+20 1000 MIPS, 1 day 1E+15 1E+10 100000 1 1 10 100 1000 王伟, 计算机工程系, 东南大学 15 5 Time complexity • The time taken by a program P t(P) = c + tP(n) • c : constant • tP : function fP (n) • n : the number of the inputs and outputs • T(n) = O(f(n)) 16 王伟, 计算机工程系, 东南大学 Compile time • Run or execution time program step a syntactically or semantically meaningful segment of a program that has a run time • Run time is independent of n 王伟, 计算机工程系, 东南大学 17 Determine the number of steps : method 1 Introduce a global variable count with initial value 0 int count=0; float sum (float a[ ], int n) { float s = 0.0; //count++ count++; for (int i = 0; i < n; i++) //count++ :