06-07-2012, 04:32 PM
Analysis of Algorithms
Analysis.pdf (Size: 119.34 KB / Downloads: 30)
Experimental Studies
Write a program
implementing the
algorithm
w Run the program with
inputs of varying size and
composition
w Use a method like
System.currentTimeMillis() to
get an accurate measure
of the actual running time
w Plot the results
Limitations of Experiments
It is necessary to implement the
algorithm, which may be difficult
w Results may not be indicative of the
running time on other inputs not included
in the experiment.
w In order to compare two algorithms, the
same hardware and software
environments must be used
Theoretical Analysis
Uses a high-level description of the
algorithm instead of an implementation
Characterizes running time as a
function of the input size, n.
Takes into account all possible inputs
Allows us to evaluate the speed of an
algorithm independent of the
hardware/software environment
Asymptotic Algorithm Analysis
w The asymptotic analysis of an algorithm determines
the running time in big-Oh notation
w To perform the asymptotic analysis
n We find the worst-case number of primitive operations
executed as a function of the input size
n We express this function with big-Oh notation
w Example:
n We determine that algorithm arrayMax executes at most
7n - 1 primitive operations
n We say that algorithm arrayMax “runs in O(n) time”
w Since constant factors and lower-order terms are
eventually dropped anyhow, we can disregard them
when counting primitive operations