文档介绍：Chapter 2
Algorithm Analysis
An algorithm is a clearly specified set of simple
instructions to be followed to solve a problem.
Algorithm analysis is the amount puter memory and
time needed to run a program (algorithm)
We use two approaches to determine it: performance analysis performance measurement
plexity: the amount of memory a
program needs to run pletion
plexity: the amount of time a
program needs to run pletion
plexity
ponents:
instruction space
data space (space needed for constants,simple ponent variables)
environment stack space (to save information needed to resume execution of pleted functions)
plexity
two parts:
a fixed part—include space for instructions,simple variables,fixed-ponent variables,constants
a variable part—include space ponent variables,dynamical allocated space,recursion stack
S(p)=c+Sp(instance characteristics)
plexity
2)example:
Sequential Search
public static int SequentialSearch( int [ ] a , int x )
{ int i;
for(i=0; i< &&a[i]!=x; i++) ;
if(i= = ) return –1;
return i;
}
plexity
Total data space:
12 bytes : x,i,a[i],0,-1,
each of them cost 2 bytes
S(n)=0
plexity
Recursive code to add a[0:n-1]
public static float Rsum(float[ ] a, int n)
{ if ( n>0 )
return Rsum(a, n-1) + a[n-1];
return 0;
}
plexity
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)
plexity
The time taken by a program p is T(p)
T(p)=compile time+run time
pile 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