(程序性能).pptVIP

Chapter 2 PROGRAM PERFORMANCE 2.1 INTRODUCTION Performance of a program is the amount of computer memory and time need to run a program. Two ways: Performance analysis – using analytical methods Performance measurement – by experiments 2.2 SPACE COMPLEXITY Space complexity of a program is the amount of memory it need s to run to completion. The amount of memory to be allocated to the program. We want to know whether or not sufficient memory is available to run the program. …… 2.2.1 Components of Space Complexity Instruction space (指令空间) Data space（数据空间） constants（存储常量） component variables（存储复合变量） Environment stack space(环境栈空间) 1. Instruction Space 4. Summary We cannot make an accurate analysis of the space requirements of a program. We can divide the space needed by a program into two parts: A fixed part A variable part The space requirement S(P) of any program S(P) = c + Sp (instance characteristics) What is the instance characteristics(实例特征) ? 2.2.2 Examples Example 2.2 Sequential search template class T int SequentialSearch(T a[ ], const T x, int n) { // Search the unordered list a[0:n-1] for x. // Return position if found; return -1 otherwise. int i; for (i = 0; i n a[i] != x; i++); if (i == n) return -1; return i; } instance characteristic： n S(p) = C + Sp(n) = 12 + 0 2.3 TIME COMPLEXITY Time complexity of a program is the amount of computer time it needs to run to completion. to provide an upper limit on the amount of time. to provide a satisfactory real-time response. to choice the better one among these solutions. 2.3.1 Components of Time Complexity T(p)= compile time + run time The compile time dose not depend on the instance characteristics. tp(n)=caADD(n)+cdSUB(n)+cmMUL(n)+cdDIV(n)+… 2.3.2 Operation Counts One way to estimate the time complexity of a program or function is to select one or more operations, such as add,multiply, and compare, and to determine how many of each is done. This method depends on our abili