4.1. performance -
analysis of algorithms
Algorithm:
a method for solving a problem that is suitable for implementation as a computer program
Basic
principle:
Scientific method (3-step approach
pay attention to cost of
observe feature of the natural world To
some running programs.
·
·
hypothesize a model that is consistent with these observations study cost, we apply
scientific methods of
predict events using this hypothesis
·
Study
the predictions by making further observations
verify aswell mathematical
·
as
·
validate by repeating until the hypothesis and observations agree analysis to derive concise
models of cost
Reasons to analyze algorithms
① Predict program behaviour The experiments we design
my program finish? be reproducible and
·
when will must
be falsifiable
will
my program finish? hypotheses
·
must
&
compare algorithms and implementations cable to be
proven false)
my program faster?
·
will this change make
·
how can I make my
program faster?
⑤ the
To develop a basis for understanding problem and for designing new algorithms
·
enables new technology
·
enables new research
Al porithmic successes
sorting
NE
·
Rearrange array of h-items in ascending order
·
used in databases, scheduling, stats, genomics, ...
·
force:N" Steps
Brute
NIOPN
·merpesort: NogN steps > enables new technology
N
, Discrete Fourier Transform
·break down waveform of N samples into periodic components
·
used in Dup, JPC6, MRI, astrophysics, ...
·
Brute force:N" Steps
· fFT algorithm: Nogn steps > enables new technology
Observations
measuring the of the stopwatch data type
exact
running time a
program: use
run a
program on various inputs
first observation: there is "problem size"
qualitative a
the problem size characterizes the difficulty of the computational task
normally, the problem size is either:
·
the size of the input or
the value of command-line
a
argument
·
the time should increase with the problem (but, by how much?)
running size
e.g. Threesum
java counts the number of triples in an
array of
integers that sums to 0
Hypotheses
·
Daniel Knuth showed that it is possible to create an accurate model that can predict program
running-time.
of:
This
requires detailed understanding
·
~ the program
~the system and computer
and advanced tools of mathematical analysis
, Log-log plot
Lop-logplot
Initial
hypothesis:
Running time approximately obeys a
power law TCN) = and standard plot
Data analysis:
Plot running time vs.
Input size N on a log-log scale
consequence
law line.
·
power
yields straight
slope b =
Refined hypothesis slope
-
Running time grows as cube of input size: aNe
/log-logplot is a
straight line with slope 3) TIN = and
Hypothesis:
time is about and with b 19(
Running =
Doubling hypothesis
xI
Quick way to estimate b in a power law hypothesis ↑
E
Run the
program, doubling the size of the input. I
↑
2
x
analysis of algorithms
Algorithm:
a method for solving a problem that is suitable for implementation as a computer program
Basic
principle:
Scientific method (3-step approach
pay attention to cost of
observe feature of the natural world To
some running programs.
·
·
hypothesize a model that is consistent with these observations study cost, we apply
scientific methods of
predict events using this hypothesis
·
Study
the predictions by making further observations
verify aswell mathematical
·
as
·
validate by repeating until the hypothesis and observations agree analysis to derive concise
models of cost
Reasons to analyze algorithms
① Predict program behaviour The experiments we design
my program finish? be reproducible and
·
when will must
be falsifiable
will
my program finish? hypotheses
·
must
&
compare algorithms and implementations cable to be
proven false)
my program faster?
·
will this change make
·
how can I make my
program faster?
⑤ the
To develop a basis for understanding problem and for designing new algorithms
·
enables new technology
·
enables new research
Al porithmic successes
sorting
NE
·
Rearrange array of h-items in ascending order
·
used in databases, scheduling, stats, genomics, ...
·
force:N" Steps
Brute
NIOPN
·merpesort: NogN steps > enables new technology
N
, Discrete Fourier Transform
·break down waveform of N samples into periodic components
·
used in Dup, JPC6, MRI, astrophysics, ...
·
Brute force:N" Steps
· fFT algorithm: Nogn steps > enables new technology
Observations
measuring the of the stopwatch data type
exact
running time a
program: use
run a
program on various inputs
first observation: there is "problem size"
qualitative a
the problem size characterizes the difficulty of the computational task
normally, the problem size is either:
·
the size of the input or
the value of command-line
a
argument
·
the time should increase with the problem (but, by how much?)
running size
e.g. Threesum
java counts the number of triples in an
array of
integers that sums to 0
Hypotheses
·
Daniel Knuth showed that it is possible to create an accurate model that can predict program
running-time.
of:
This
requires detailed understanding
·
~ the program
~the system and computer
and advanced tools of mathematical analysis
, Log-log plot
Lop-logplot
Initial
hypothesis:
Running time approximately obeys a
power law TCN) = and standard plot
Data analysis:
Plot running time vs.
Input size N on a log-log scale
consequence
law line.
·
power
yields straight
slope b =
Refined hypothesis slope
-
Running time grows as cube of input size: aNe
/log-logplot is a
straight line with slope 3) TIN = and
Hypothesis:
time is about and with b 19(
Running =
Doubling hypothesis
xI
Quick way to estimate b in a power law hypothesis ↑
E
Run the
program, doubling the size of the input. I
↑
2
x
