Today’s topicsComputing factorialFibonacci numbersA contrast to (fact n): computing FibonacciA contrast: computing FibonacciComputing Fibonacci: putting it in contextAn overview of this lectureMeasuring the time complexity of a functionAn example: factorialExpanding the recurrenceSlide 11A second example: Computing FibonacciLooking at the RecurrenceDifferent Rates of GrowthAsymptotic NotationSlide 16Theta, Big-O, Little-oMotivationSome common orders of growthSlide 20A general result: linear growthConnecting orders of growth to algorithm designSlide 23Slide 24The order of growth of my-exptUsing different processes for the same goalThe order of growth of new-exptSlide 28A general result: logarithmic growthSlide 30Back to FibonacciAnother general result: exponential growthWhy is our version of fib so inefficient?Slide 34The computation tree for (fib 7)An efficient implementation of Fibonacciifib is now linearHow much space (memory) does a procedure require?Tracing factorialSlide 40A contrast: iterative factorialSlide 42SummarySlide 44Towers of HanoiSlide 46A tree recursionOrders of growth for towers of HanoiAnother example of different processesPascal’s trianglePascal’s triangle the traditional waySlide 52Slide 53Solving the same problem a different waySlide 55Slide 56Slide 57Solving the same problem the direct waySlide 59So why do these orders of growth matter?6.001 SICP1/4301/14/19Today’s topics•Orders of growth of processes•Relating types of procedures to different orders of growth6.001 SICP2/4301/14/19Computing factorial(define (fact n) (if (= n 0) 1 (* n (fact (- n 1)))))•We can run this for various values of n:(fact 10)(fact 100)(fact 1000)(fact 10000)•Takes longer to run as n gets larger, but still manageable for large n (e.g. n = 10000 – takes about 13 seconds of “real time” in DrScheme; while n = 1000 – takes about 0.2 seconds of “real time”)6.001 SICP3/4301/14/19Fibonacci numbersThe Fibonacci numbers are described by the following equations:fib(0) = 0fib(1) = 1fib(n) = fib(n-2) + fib(n-1) for n ≥ 2Expanding this sequence, we getfib(0) = 0fib(1) = 1fib(2) = 1fib(3) = 2fib(4) = 3fib(5) = 5fib(6) = 8fib(7) = 13...6.001 SICP4/4301/14/19A contrast to (fact n): computing Fibonacci(define (fib n) (if (= n 0) 0 (if (= n 1) 1 (+ (fib (- n 1)) (fib (- n 2))))))•We can run this for various values of n:(fib 10)(fib 20)(fib 100)(fib 1000)•These take much longer to run as n gets larger6.001 SICP5/4301/14/19A contrast: computing Fibonacci(define (fib n) (if (= n 0) 0 (if (= n 1) 1 (+ (fib (- n 1)) (fib (- n 2))))))•Later we’ll see that when calculating (fib n), we need more than 2n/2 addition operations(fib 100) uses + at least 250 times(fib 2000) uses + at least 21000 times= 1,125,899,906,842,624=10,715,086,071,862,673,209,484,250,490,600,018,105,614,048,117,055,336,074,437, 503,883,703,510,511,249,361,224,931,983,788,156,958,581,275,946,729,175,531,468, 251,871,452,856,923,140,435,984,577,574,698,574,803,934,567,774,824,230,985,421, 074,605,062,371,141,877,954,182,153,046,474,983,581,941,267,398,767,559,165,543, 946,077,062,914,571,196,477,686,542,167,660,429,831,652,624,386,837,205,668,069, 3766.001 SICP6/4301/14/19Computing Fibonacci: putting it in context•A rough estimate: the universe is approximately 1010 years = 3x1017 seconds old•Fastest computer around (not your laptop) can do about 280x1012 arithmetic operations a second, or about 1032 operations in the lifetime of the universe•2100 is roughly 1030•So with a bit of luck, we could run (fib 200) in the lifetime of the universe …•A more precise calculation gives around 1000 hours to solve (fib 100)•That is 1000 6.001 lectures, or 40 semesters, or 20 years of 6.001 or …6.001 SICP7/4301/14/19An overview of this lecture•Measuring time requirements (complexity) of a function•Simplifying the time complexity with asymptotic notation•Calculating the time complexity for different functions•Measuring space complexity of a function6.001 SICP8/4301/14/19Measuring the time complexity of a function•Suppose n is a parameter that measures the size of a problem•For fact and fib, n is just the procedure’s parameter•Let t(n) be the amount of time necessary to solve a problem of size n•What do we mean by “the amount of time”? How do we measure “time”?•Typically, we will define t(n) to be the number of primitive operations (e.g. the number of additions) required to solve a problem of size n6.001 SICP9/4301/14/19An example: factorial(define (fact n) (if (= n 0) 1 (* n (fact (- n 1)))))•Define t(n) to be the number of multiplications required by (fact n)•By looking at fact, we can see that:t(0) = 0t(n) = 1 + t(n-1) for n ≥ 1•In other words: solving (fact n) for any n ≥ 1 requires one more multiplication than solving (fact (- n 1))6.001 SICP10/4301/14/19Expanding the recurrencet(0) = 0t(n) = 1 + t(n-1) for n>=1t(0) = 0t(1) = 1 + t(0) = 1t(2) = 1 + t(1) = 2t(3) = 1 + t(2) = 3…In general:t(n) = n6.001 SICP11/4301/14/19Expanding the recurrencet(0) = 0t(n) = 1 + t(n-1) for n>=1•How would we prove that t(n) = n for all n?•Proof by induction (remember from last lecture?):•Base case: t(n) = n is true for n = 0•Inductive step: if t(n) = n then it follows that t(n+1) = n+1•Hence by induction this is true for all n6.001 SICP12/4301/14/19A second example: Computing Fibonacci(define (fib n) (if (= n 0) 0 (if (= n 1) 1 (+ (fib (- n 1)) (fib (- n 2))))))•Define t(n) to be the number of primitive operations (=,+,-) required by (fib n)•By looking at fib, we can see that:t(0) = 1t(1) = 2t(n) = 5 + t(n-1) + t(n-2) for n ≥ 2•In other words: solving (fib n) for any n ≥ 2 requires 5 more primitive ops than solving (fib (- n 1)) and solving (fib (- n 2))6.001 SICP13/4301/14/19Looking at the Recurrencet(0) = 1t(1) = 2t(n) = 5 + t(n-1) + t(n-2) for n ≥ 2•We can see that t(n) ≥ t(n-1) for all n ≥ 2•So, for n ≥ 2, we havet(n) = 5 + t(n-1) + t(n-2) ≥ 2 t(n-2)•Every time n increases by 2, we more than double the number of primitive ops that are required•If we iterate the argument, we gett(n) ≥ 2 t(n-2) ≥ 4 t(n-4) ≥ 8 t(n-6) ≥ 16 t(n-8) …•A little more math shows thatt(n) ≥ 2n/26.001 SICP14/4301/14/19Different Rates of Growth•So what does it really mean for things to grow at different
View Full Document
Unlocking...