《数据结构的算法在C++中的应用》（英文版）Chapter 2 Program performance

Chapter 2 Program performance

Chapter 2 Program performance

2.1 Preface Performance of a program: the amount of computer memory and time needed to run a program We use two approaches to determine it performance analysIs performance measurement

2.1 Preface Performance of a program: the amount of computer memory and time needed to run a program We use two approaches to determine it: performance analysis performance measurement

2.1 Preface Space complexity: the amount of memory a program needs to run to completion Time complexity the amount of time a program needs to run to completion

2.1 Preface Space complexity: the amount of memory a program needs to run to completion Time complexity: the amount of time a program needs to run to completion

2.2 Space Complexity 1) components Instruction space data space (space needed for constants, simple variables, component variables environment stack space( to save information needed to resume execution of partially completed nctions

2.2 Space Complexity 1)components: instruction space data space (space needed for constants,simple variables,component variables) environment stack space (to save information needed to resume execution of partially completed functions)

2.2 Space Complexity two parts a fixed part--include space for instructions, simple variables fixed-size component variables. constants a variable part--include space for component variables, dynamical allocated space, recursion stack S(p=C+S,(instance characteristics)

2.2 Space Complexity two parts: a fixed part—include space for instructions,simple variables,fixed-size component variables,constants a variable part—include space for component variables,dynamical allocated space,recursion stack S(p)=c+Sp (instance characteristics)

2.2 Space Complexity 2 )example Sequential Search(program 2.1) Template int Sequential Search(T all, const T&x, int n) int 1 for(i=0;i<n&&a[i]!x,i++); If(i==return return 1

2.2 Space Complexity 2)example: • Sequential Search (program 2.1) Template int SequentialSearch(T a[], const T&x, int n) { int i; for(i=0; i<n&&a[i]!=x; i++) ; If(i= =n)return –1; return i; }

2.2 Space Complexity Total data space 12 bytes( x, i, a[1],,-1, n, each of them cost 2 bytes)

2.2 Space Complexity Total data space: 12 bytes( x,i,a[i],0,-1,n, each of them cost 2 bytes) S(n)=0

2.2 Space Complexity Recursive code to add a[0 n-1(Program 1.9) Template T Rsumtal l, int n) f if(n>0 return Rsum (a, n-1)+an-1 return 0

2.2 Space Complexity • Recursive code to add a[0:n-1] (Program 1.9) Template T Rsum(T a[ ], int n) { if ( n>0 ) return Rsum(a, n-1) + a[n-1]; return 0; }

2.2 Space Complexity Recursion stack space formal parameters: a(2 byte), n (2 byte) return address(2 byte) Depth of recursion: n+1 SSum(n)=6(n+1)

2.2 Space Complexity Recursion stack space: formal parameters : a (2 byte), n(2 byte) return address(2 byte) Depth of recursion: n+1 SRsum(n)=6(n+1)

2.3 Time complexity The time taken by a program p is t(p) T(p=compile timetrun time The compile time does not depend on the instance characteristics The run time is denoted by t(instance characteristics) D)operation counts identify one or more key operations and determine the num ber of times these are performed

2.3 Time complexity The time taken by a program p is T(p) T(p)=compile time+run time The compile time does not depend on the instance characteristics The run time is denoted by tp (instance characteristics) 1)operation counts identify one or more key operations and determine the number of times these are performed