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
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
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+Sp(instance characteristics)
2.2 Space Complexity
2)example,
? Sequential Search (program 2.1)
Template<class T>
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[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 <class T> 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
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 a[0:n-1]
template<class T>
int Max(T a[],int n)
{//locate the largest element in a[0:n-1]
int pos=0;
for(int i=1;i<n;i++)
if(a[pos]<a[i]) 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<class T>
void SelectionSort(T a[],int n)
{//sort the n number in a[0:n-1].
for(int size=n;size>1;size--)
{int j=Max(a,size);
swap(a[j],a[size-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<class T>
void Bubble(T a[],int n)
{//Bubble largest element in a[0:n-1] to right
for(int i=0;i<n-1;i++)
if(a[i]>a[i+1])swap(a[i],a[i+1]);
}
2.3 Time Complexity
Template<class T>
void BubbleSort(T a[],int n)
{//Sort a[0:n-1] using a bubble sort
for(int i=n;i>1;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 sort
2.3 Time Complexity
Example 2.9,2.15(program 2.5&2.11)
Rank sort
template<class T>
void Rank(T a[],int n,int r[])
{//Rank the n elements a[0:n-1]
for(int i=0;i<n;i++)
r[i]=0;//initialize
//compare all element pairs
for(int i=1;i<n;i++)
for(int j=0;j<i;j++)
if(a[j]<=a[i]) r[i]++;
else r[j]++;
}
2.3 Time Complexity
Template<class T>
void Rearrange(T a[],int n,int r[])
{//In-place rearrangement into sorted order
for(int i=0;i<n;i++)
//get proper element to a[i]
while(r[i]!=i){
int t=r[i];
swap(a[i],a[t]);
swap(r[i],r[t]);
}
}
2.3 Time Complexity
Analysis of rank sort
the number of element comparison is,
(n-1)*n/2
the number of element move is 2n
2.3 Time Complexity
Best,Worst,and Average Operation Counts
? The 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<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;
}
2.3 Time Complexity
Analysis of Sequential Search
? For 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)/2
i=1
n
2.3 Time Complexity
Example 2.18(program2.14)
insertion sort
Template<class T>
void Insert(T a[],int n,const T&x)
{//Insert x into the sorted array a[0:n-1]
int i;
for(i=n-1;i>=0&&x<a[i];i--)
a[i+1]=a[i];
a[i+1]=x;
}
2.3 Time Complexity
Template<class T>
Void InsertionSort(T a[],int n)
{//sort a[0:n-1]
for(int i=0; i<n; i++)
{
T t=a[i];
Insert(a,i,t);
}
}
2.3 Time Complexity
Another version of insertion sort
template<class T>
void InsertionSort(T a[],int n)
{for(int i=0;i<n;i++) {
//insert a[i] into a[0:n-1]
T t=a[i];
int j;
for(j=i-1;j>=0&&t<a[j];j--)
a[j+1]=a[j];
a[j+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 steps
2.3 Time Complexity
Counting step in Program 1.8(Program 2.16)
template <class T> T Sum(T a[],int n)
{ T tsum = 0 ;
count++;
for (int i = 0 ; i<n ; i++)
{ count++;
tsum += a[i] ; 2n+3 step
count++;
}
count++;
count++; return tsum;
}
2.3 Time Complexity
? There 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.22[sequential search]
1)best-case step count
Statement s/e Frequency Total steps
int SequentialSearch(Ta[],T&x,int n) 0 0 0
{ 0 0 0
int i; 1 1 1
for(int i=0;i<n&&a[i]!=x;i++) 1 1 1
if(i= =n)return –1; 1 1 1
return i; 1 1 1
} 0 0 0
Total 4
2.3 Time Complexity
2).worst-case step count
Statement s/e Frequency Total steps
int SequentialSearch(Ta[],T&x,int n) 0 0 0
{ 0 0 0
int i; 1 1 1
for(int i=0;i<n&&a[i]!=x;i++) 1 n+1 n+1
if(i= =n)return –1; 1 1 1
return i; 1 0 0
} 0 0 0
Total n+3
2.3 Time Complexity
3).step count when x=a[j]
Statement s/e Frequency Total steps
int SequentialSearch(Ta[],T&x,int n) 0 0 0
{ 0 0 0
int i; 1 1 1
for(int i=0;i<n&&a[i]!=x;i++) 1 j+1 j+1
if(i= =n)return –1; 1 1 1
return i; 1 1 1
} 0 0 0
Total j+4
2.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)<=cg(n) for all n,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 Complexity
Example 1,Selection sort
a[0],a[1],…,a[n -1] Frequency
for (int i=0 ; i < n-1 ; i++) n
{ int k= i; n-1
for (int j=i+1; j<n ; j++) (n2+n-2)/2
if (a[j]<a[k]) k=j; <=(n2-n)/2
int temp=a[i]; a[i]=a[k]; a[k]=temp; 3(n-1)
}
2.3 Time Complexity
Example 2,Binary Search(Program 2-30)
template<class T> int BinarySearch(T a[],const T & x,int n)
{ int left=0; int right = n-1;
while (left<=right)
{ int middle = (left+right)/2;
if (x==a[middle]) return middle;
if (x>a[middle]) 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>=n0
2.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)<=c2g(n) for all n,
n>=n0