keywords(50m):
- performance of algorithms(12 times)
- running time(7 times) shortest time
- performance prediction
- scientific method(4 times)
How to make mathematical models and how to classify algorithms according to the order of growth of their running time.
Different perspectives
| role | perspective |
|---|---|
| Programmer | needs to develop a working solution(algorithm designer) |
| Client | wants to solve problem efficiently(algorithm user) |
| Theoretician | wants to understand(algorithm prover) |
| Team | basic blocking and tackling |
| Student | may play all the roles |
Running time
“ As soon as an Analytic Engine exists, it will necessarily guide the future
course of the science. Whenever any result is sought by its aid, the question will arise—By what course of calculation can these results be arrived at by the machine in the shortest time? ” — Charles Babbage (1864)
Reasons to analyze algorithms
- Predict performance.
- Compare algorithms.
- Provide guarantees.
- Understand theoretical basis.
Primary practical reason: avoid performance bugs.
And it's very, very frequent to see, in today's computational infrastructure, a situation where the client gets bad performance, because the programmer did not understand the performance characteristics of the algorithm.
Some algorithmic successes
Discrete Fourier transform.
- Break down waveform of N samples into periodic components.
- Applications: DVD, JPEG, MRI, astrophysics, ….
- Brute force: N^2 steps.
- FFT algorithm: N log N steps, enables new technology.
N-body simulation.
- Simulate gravitational interactions among N bodies.
- Brute force: N 2 steps.
- Barnes-Hut algorithm: N log N steps, enables new research
The challenge
Q: will my program be able to solve a large practical input?
- why is my program running so slowly?
- Why does it run out of memory?
Insight. [Knuth 1970s] Use scientific method to understand performance.
Scientific approach to applied to analysis of algorithms
A framework for predicting performance and comparing algorithms.
Scientific method
- Observe some feature of the natural world.
- Hypothesize a model that is consistent with the observations.
- Predict events using the hypothesis.
- Verify the predictions by making further(more) observations.
- Validate by repeating until the hypothesis and observations agree.
Basic principles
Principles.
- Experiments must be reproducible.
- Hypotheses must be falsifiable.And also the hypotheses have to have a specific property that the experiment can show the hypothesis to be wrong.
