《精品数据结构Programperformance》由会员分享，可在线阅读，更多相关《精品数据结构Programperformance（39页珍藏版）》请在金锄头文库上搜索。
1、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
2、 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 fu
3、nctions) 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)exampl
4、e: 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
5、 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)=compil
6、e 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 t
7、he 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
8、 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 comparison
9、s, 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 Temp
10、late 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
11、 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 el
12、ement 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 de
13、termine.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
14、;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 voi
15、d 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
16、 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
17、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 t
18、sum; 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 invocati
19、on 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
20、 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 Freq
21、uency 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 chara
22、cteristics.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(2
23、n), 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
24、 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
25、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
