Algorithms, 4th Edition·Robert Sedgewick and Kevin Wayne·Copyright © 2002–2011·February 8, 2012 5:59:31 AMAlgorithmsFOUR T H EDIT IONR O B E R T S EDG EWICK K EVIN W A Y N E‣observations‣mathematical models‣order-of-growth classifications‣dependencies on inputs‣memory1.4 ANALYSIS OF ALGORITHMSCast of characters2Programmer needs to developa working solution.Client wants to solveproblem efficiently.Theoretician wants to understand.Basic blocking and tacklingis sometimes necessary.[this lecture]Student might playany or all of theseroles someday.3Running timeAnalytic Enginehow many times do you have to turn the crank?“ 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)Predict performance.Compare algorithms.Provide guarantees.Understand theoretical basis.Primary practical reason: avoid performance bugs. Reasons to analyze algorithms4this course (COS 226)theory of algorithms (COS 423)client gets poor performance because programmerdid not understand performance characteristics5Some algorithmic successesDiscrete 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.Friedrich Gauss18058T16T32T64Ttime1K 2K 4K 8Ksizequadraticlinearithmiclinear6Some algorithmic successesN-body simulation.•Simulate gravitational interactions among N bodies.•Brute force: N 2 steps.•Barnes-Hut algorithm: N log N steps, enables new research.Andrew AppelPU '81 8T16T32T64Ttime1K 2K 4K 8KsizequadraticlinearithmiclinearQ. Will my program be able to solve a large practical input?Key insight. [Knuth 1970s] Use scientific method to understand performance.The challenge7Why is my program so slow ? Why does it run out of memory ?8Scientific method applied to analysis of algorithmsA 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.9‣observations‣mathematical models‣order-of-growth classifications‣dependencies on inputs‣memory10Example: 3-sum3-sum. Given N distinct integers, how many triples sum to exactly zero?Context. Deeply related to problems in computational geometry.% more 8ints.txt830 -40 -20 -10 40 0 10 5% java ThreeSum 8ints.txt4a[i]a[j]a[k]sum30-4010030-20-100-404000-1001001234public 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++) for (int k = j+1; k < N; k++) if (a[i] + a[j] + a[k] == 0) count++; return count; } public static void main(String[] args) { int[] a = In.readInts(args[0]); StdOut.println(count(a)); }} 113-sum: brute-force algorithmcheck each triplefor simplicity, ignore integer overflowQ. How to time a program?A. Manual.12Measuring the running time% java ThreeSum 1Kints.txt70% java ThreeSum 2Kints.txt% java ThreeSum 4Kints.txt5284039tick tick tickObserving the running time of a programtick tick tick tick tick tick tick ticktick tick tick tick tick tick tick ticktick tick tick tick tick tick tick ticktick tick tick tick tick tick tick ticktick tick tick tick tick tick tick ticktick tick tick tick tick tick tick ticktick tick tick tick tick tick tick ticktick tick tick tick tick tick tick ticktick tick tick tick tick tick tick ticktick tick tick tick tick tick tick ticktick tick tick tick tick tick tick ticktick tick tick tick tick tick tick ticktick tick tick tick tick tick tick ticktick tick tick tick tick tick tick ticktick tick tick tick tick tick tick ticktick tick tick tick tick tick tick ticktick tick tick tick tick tick tick ticktick tick tick tick tick tick tick ticktick tick tick tick tick tick tick ticktick tick tick tick tick tick tick ticktick tick tick tick tick tick tick ticktick tick tick tick tick tick tick ticktick tick tick tick tick tick tick ticktick tick tick tick tick tick tick ticktick tick tick tick tick tick tick ticktick tick tick tick tick tick tick ticktick tick tick tick tick tick tick tickQ. How to time a program?A. Automatic.13Measuring the running timeclient codepublic static void main(String[] args){ int[] a = In.readInts(args[0]); Stopwatch stopwatch = new Stopwatch(); StdOut.println(ThreeSum.count(a)); double time = stopwatch.elapsedTime();} public class Stopwatch public class StopwatchStopwatch()Stopwatch()create a new stopwatchdoubleelapsedTime()elapsedTime()time since creation (in seconds)(part of stdlib.jar )Run the program for various input sizes and measure running time.14Empirical analysisNtime (seconds) †2500.05000.01,0000.12,0000.84,0006.48,00051.116,000?Standard plot. Plot running time T (N) vs. input size N.15Data analysis1K.1.2.4.81.63.26.412.825.651.2Analysis of experimental data (the running time of ThreeSum)log-log plotstandard plotlgNproblem size N2K 4K 8Klg(T(N))running time T(N)1K10203040502K 4K 8Kstraight lineof slope 3Log-log plot. Plot running time T (N) vs. input size N using log-log scale.Regression. Fit straight line through data points: a N b.Hypothesis. The running time is about 1.006 × 10 –10 × N 2.999 seconds.16Data analysisslopepower law1K.1.2.4.81.63.26.412.825.651.2Analysis of experimental data (the running time of ThreeSum)log-log plotstandard plotlgNproblem size N2K 4K 8Klg(T(N))running time T(N)1K10203040502K 4K 8Kstraight lineof slope 3lg(T (N)) = b lg N + cb = 2.999c = -33.2103T (N) = a N b, where a = 2 c17Prediction and validationHypothesis. The running time is about 1.006 × 10 –10 × N 2.999 seconds.Predictions.•51.0 seconds for N = 8,000.•408.1 seconds for N = 16,000.Observations.validates hypothesis!Ntime (seconds) †8,00051.18,00051.08,00051.116,000410.8"order of growth" of runningtime is about N3 [stay tuned]Doubling
View Full Document
Unlocking...