Question? Leave a message!




ANALYSIS OF ALGORITHMS

ANALYSIS OF ALGORITHMS
Dr.AlexanderTyler Profile Pic
Dr.AlexanderTyler,India,Teacher
Published Date:21-07-2017
Website URL
Comment
ROBERT SEDGEWICK KEVIN WAYNE Algorithms 1.4 ANALYSIS OF ALGORITHMS introduction ‣ observations ‣ mathematical models ‣ Algorithms FOUR TH EDITION order-of-growth classifications ‣ theory of algorithms ‣ ROBERT SEDGEWICK KEVIN WAYNE http://algs4.cs.princeton.edu memory ‣1.4 ANALYSIS OF ALGORITHMS introduction ‣ observations ‣ mathematical models ‣ Algorithms order-of-growth classifications ‣ theory of algorithms ‣ ROBERT SEDGEWICK KEVIN WAYNE http://algs4.cs.princeton.edu memory ‣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) how many times do you have to turn the crank? Analytic Engine 3Cast of characters Programmer needs to develop a working solution. Student might play any or all of these Client wants to solve roles someday. problem efficiently. Theoretician wants to understand. 4Reasons to analyze algorithms Predict performance. this course (COS 226) Compare algorithms. Provide guarantees. theory of algorithms (COS 423) Understand theoretical basis. Primary practical reason: avoid performance bugs. client gets poor performance because programmer did not understand performance characteristics 5Some algorithmic successes Discrete Fourier transform. Break down waveform of N samples into periodic components. Applications: DVD, JPEG, MRI, astrophysics, …. 2 Brute force: N steps. Friedrich Gauss 1805 FFT algorithm: N log N steps, enables new technology. time quadratic 64T 32T 16T linearithmic 8T linear size 1K 2K 4K 8K 6Some algorithmic successes N-body simulation. Simulate gravitational interactions among N bodies. 2 Brute force: N steps. Barnes-Hut algorithm: N log N steps, enables new research. Andrew Appel PU '81 time quadratic 64T 32T 16T linearithmic 8T linear size 1K 2K 4K 8K 7The challenge Q. Will my program be able to solve a large practical input? Why does it run out of memory ? Why is my program so slow ? Insight. Knuth 1970s Use scientific method to understand performance. 8Scientific method 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 observations. Validate by repeating until the hypothesis and observations agree. Principles. Experiments must be reproducible. Hypotheses must be falsifiable. Feature of the natural world. Computer itself. 91.4 ANALYSIS OF ALGORITHMS introduction ‣ observations ‣ mathematical models ‣ Algorithms order-of-growth classifications ‣ theory of algorithms ‣ ROBERT SEDGEWICK KEVIN WAYNE http://algs4.cs.princeton.edu memory ‣Example: 3-SUM 3-SUM. Given N distinct integers, how many triples sum to exactly zero? ai aj ak sum % more 8ints.txt 8 30 -40 10 0 1 30 -40 -20 -10 40 0 10 5 30 -20 -10 0 2 % java ThreeSum 8ints.txt 3 -40 40 0 0 4 4 -10 0 10 0 Context. Deeply related to problems in computational geometry. 113-SUM: brute-force algorithm public class ThreeSum public static int count(int a) int N = a.length; int count = 0; for (int i = 0; i N; i++) for (int j = i+1; j N; j++) check each triple for (int k = j+1; k N; k++) for simplicity, ignore if (ai + aj + ak == 0) integer overflow count++; return count; public static void main(String args) In in = new In(args0); int a = in.readAllInts(); StdOut.println(count(a)); 12Measuring the running time Q. How to time a program? % java ThreeSum 1Kints.txt A. Manual. tick tick tick 70 % java ThreeSum 2Kints.txt tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick 528 % java ThreeSum 4Kints.txt tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick tick 4039 13 Observing the running time of a programMeasuring the running time Q. How to time a program? A. Automatic. (part of stdlib.jar ) public class Stopwatch public class Stopwatch Stopwatch() Stopwatch() create a new stopwatch double elapsedTime() elapsedTime() time since creation (in seconds) public static void main(String args) In in = new In(args0); int a = in.readAllInts(); Stopwatch stopwatch = new Stopwatch(); StdOut.println(ThreeSum.count(a)); client code double time = stopwatch.elapsedTime(); StdOut.println("elapsed time " + time); 14Empirical analysis Run the program for various input sizes and measure running time. 15Empirical analysis Run the program for various input sizes and measure running time. † N time (seconds) 250 0.0 500 0.0 1,000 0.1 2,000 0.8 4,000 6.4 8,000 51.1 16,000 ? 16Data analysis Standard plot. Plot running time T (N) vs. input size N. standard plot log-log plot 51.2 50 straight line of slope 3 25.6 40 12.8 6.4 30 3.2 1.6 20 .8 .4 10 .2 .1 1K 2K 4K 8K 1K 2K 4K 8K problem size N lgN Analysis of experimental data (the running time of ThreeSum) 17 running time T(N) lg(T(N))Data analysis Log-log plot. Plot running time T (N) vs. input size N using log-log scale. standard plot log-log plot 51.2 50 straight line of slope 3 25.6 40 12.8 lg(T (N)) = b lg N + c 6.4 b = 2.999 30 3.2 c = -33.2103 1.6 b c T (N) = a N , where a = 2 20 .8 .4 3 orders of magnitude 10 .2 .1 1K 2K 4K 8K 1K 2K 4K 8K problem size N lgN Analysis of experimental data (the running time of ThreeSum) power law slope b Regression. Fit straight line through data points: a N . –10 2.999 Hypothesis. The running time is about 1.006 × 10 × N seconds. 18 running time T(N) lg(T(N))Prediction and validation –10 2.999 Hypothesis. The running time is about 1.006 × 10 × N seconds. "order of growth" of running 3 time is about N stay tuned Predictions. 51.0 seconds for N = 8,000. 408.1 seconds for N = 16,000. Observations. † N time (seconds) 8,000 51.1 8,000 51.0 8,000 51.1 16,000 410.8 validates hypothesis 19Doubling hypothesis Doubling hypothesis. Quick way to estimate b in a power-law relationship. Run program, doubling the size of the input. † N time (seconds) ratio lg ratio b T(2N) a(2N) = b T(N) aN 250 0.0 – b =2 500 0.0 4.8 2.3 1,000 0.1 6.9 2.8 2,000 0.8 7.7 2.9 lg (6.4 / 0.8) = 3.0 4,000 6.4 8.0 3.0 8,000 51.1 8.0 3.0 seems to converge to a constant b ≈ 3 b Hypothesis. Running time is about a N with b = lg ratio. Caveat. Cannot identify logarithmic factors with doubling hypothesis. 20