Chapter 2Program performance2.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.2 Space Complexity1)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 partinclude space for instructions,simple variables,fixed-size component variables,constants a variable partinclude space for component variables,dynamical allocated space,recursion stack S(p)=c+Sp(instance characteristics)2.2 Space Complexity2)example: Sequential Search (program 2.1)Templateint SequentialSearch(T a, const T&x, int n) int i; for(i=0; in&ai!=x; i+) ; If(i= =n)return 1; return i;2.2 Space Complexity Total data space: 12 bytes( x,i,ai,0,-1,n, each of them cost 2 bytes) S(n)=02.2 Space ComplexityRecursive code to add a0:n-1 (Program 1.9) Template T Rsum(T a , int n) if ( n0 ) return Rsum(a, n-1) + an-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 SRsum(n)=6(n+1)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 2.3 Time Complexity Example 2.7(program1.31) finding the largest number in a0:n-1 template int Max(T a,int n) /locate the largest element in a0:n-1 int pos=0; for(int i=1;in;i+) if(aposai) pos=i; return pos;2.3 Time Complexity Analysis of Max function: each iteration of the for loop makes one comparison, so the total number of element comparison is n-1 2.3 Time Complexity Example 2.11(program 2.7) selection sort template void SelectionSort(T a,int n) /sort the n number in a0:n-1. for(int size=n;size1;size-) int j=Max(a,size); swap(aj,asize-1); 2.3 Time Complexity Analysis of selection sort 1)each invocation Max(a,size)results in size-1 comparisons, so the total number of comparisons is : n-1+n-2+3+2+1=(n-1)*n/2 2)the number of element move is 3(n-1)2.3 Time Complexity Example 2.12(program 2.8&2.9) bubble sort template void Bubble(T a, int n) /Bubble largest element in a0:n-1 to right for(int i=0;iai+1)swap(ai,ai+1); 2.3 Time Complexity Template void BubbleSort(T a,int n) /Sort a0:n-1 using a bubble sort for(int i=n;i1;i-) Bubble(a,i); 2.3 Time Complexity Analysis of bubble sort the number of element comparisons is (n-1)*n/2,as for selection sort2.3 Time Complexity Example 2.9,2.15(program 2.5&2.11) Rank sort template void Rank(T a,int n,int r) /Rank the n elements a0:n-1 for(int i=0;in;i+) ri=0;/initialize /compare all element pairs for(int i=1;in;i+) for(int j=0;ji;j+) if(aj=ai) ri+; else rj+; 2.3 Time Complexity Template void Rearrange(T a,int n,int r) /In-place rearrangement into sorted order for(int i=0;in;i+) /get proper element to ai while(ri!=i) int t=ri; swap(ai,at); swap(ri,rt); 2.3 Time Complexity Analysis of rank sort the number of element comparison is : (n-1)*n/2 the number of element move is 2n2.3 Time Complexity Best,Worst,and Average Operation CountsThe average operation count is often quite difficult to determine.As a result,we limit our analysis to determining the best and worst counts.2.3 Time Complexity Example 2.13(program 2.1) Sequential Search Template int SequentialSearch(T a, const T&x, int n) /search the unordered list a0:n-1 for x /return position if found;return 1 otherwise; int i; for(i=0;in&ai!=x;i+) if(i=n)return-1; return i; 2.3 Time Complexity Analysis of Sequential SearchFor successful searches,the best comparison count is one, the worst is n.The average count for a successful search is: (1/n)i=(n+1)/2i=1n2.3 Time Complexity Example 2.18(program2.14) insertion sort Template void Insert(T a, int n, const T&x) /Insert x into the sorted array a0:n-1 int i; for(i=n-1;i=0&xai;i-) ai+1=ai; ai+1=x; 2.3 Time Complexity Template Void InsertionSort(T a, int n)/sort a0:n-1 for(int i=0; in; i+) T t=ai; Insert(a,i,t); 2.3 Time Complexity Another version of insertion sort template void InsertionSort(T a,int n) for(int i=0;i=0&taj;j-) aj+1=aj; aj+1=t; 2.3 Time Complexity Analysis of insertion sort both version perform the same number of comparisons. the best case is n-1 the worst case is (n-1)*n/2 the average case:2.3 Time Complexity 2)Step counts to account for the time spent in all parts of the program/function. we create a global variable count to determine the number of steps2.3 Time Complexity Counting step in Program 1.8(Program 2.16)template T Sum(T a, int n) T tsum = 0 ; count+; for (int i = 0 ; in ; i+) count+; tsum += ai ; 2n+3 step count+; count+; count+; return tsum; 2.3 Time ComplexityThere is an important difference between the step count of a statement and its steps per execution(s/e)The step count does not necessarily reflect the complexity of the statement.For example: x=sum(a,m) has the step count of one; because the change resulting from the invocation of Sum is 2m+3,the steps per execution is 1+(2m+3)=2m+4.2.3 Time Complexity Example 2.22sequential search 1)best-case step count Statement s/e Frequency Total stepsint SequentialSearch(Ta,T&x,int n) 0 0 0 0 0 0 int i; 1 1 1 for(int i=0;in&ai!=x;i+) 1 1 1 if(i= =n)return 1; 1 1 1 return i; 1 1 1 0 0 0Total 42.3 Time Complexity2).worst-case step countStatement s/e Frequency Total stepsint SequentialSearch(Ta,T&x,int n) 0 0 0 0 0 0 int i; 1 1 1 for(int i=0;in&ai!=x;i+) 1 n+1 n+1 if(i= =n)return 1; 1 1 1 return i; 1 0 0 0 0 0Total n+32.3 Time Complexity 3).step count when x=ajStatement s/e Frequency Total stepsint SequentialSearch(Ta,T&x,int n) 0 0 0 0 0 0 int i; 1 1 1 for(int i=0;in&ai!=x;i+) 1 j+1 j+1 if(i= =n)return 1; 1 1 1 return i; 1 1 1 0 0 0Total j+42.3 Time Complexity 3).Asymptotic Notation(O, , , o): describes the behavior of the time or space complexity for large instance characteristics.2.3 Time Complexity I )Big Oh Notation(O): provide a upper bound for the function f. Definition: f(n)=O(g(n) iff positive constant c and n0 exist such that f(n)=n0 For example: linear function f(n)=3n+2. when n=2,3n+2=3n+n=4n, so f(n)=O(n); Quadratic function O(n2),exponential functionO(2n), constant functionO(c)2.3 Time ComplexityExample 1: Selection sort a0,a1,an-1 Frequency for (int i=0 ; i n-1 ; i+) n int k= i; n-1 for (int j=i+1; jn ; j+) (n2+n-2)/2 if (ajak) k=j; =(n2-n)/2 int temp=ai; ai=ak; ak=temp; 3(n-1) 2.3 Time ComplexityExample 2: Binary Search(Program 2-30)template int BinarySearch(T a, const T & x, int n) int left=0; int right = n-1; while (leftamiddle) left=middle+1; else right= middle-1; return -1; 2.3 Time Complexity II).Omega Notation (): is the lower bound analog of the big Oh notation,permits us to bound the value f from below. Definition: f(n)= (g(n) iff positive constant c and n0 exist such that f(n)=cg(n) for all n, n=n02.3 Time Complexity III).Theta Notation(): is used when the function f can be bounded both from above and below by the same function g. Definition : f(n)= (g(n) iff positive constants c1 and c2 and a n0 exist such that c1g(n)=f(n)=n0