CS61A Lecture 6Clicker Test How long does a function take to run?AssumptionsColleen’s Morning RoutineConstant RuntimeSlide 7DemoSlide 9Write a constant runtime procedure? (Brushing your teeth)Linear RuntimeSlide 12Slide 13Slide 14Write a linear runtime procedure? (Swimming laps)What is the runtime of this?Slide 17Problem Solving Tip!Linear * Linear (Quadratic) RuntimeLinear * Linear Runtime (quadratic) (Reading Piazza)Slide 21Slide 22Slide 23PowerPoint PresentationWrite a linear*linear (quadratic) runtime procedure? (Reading Piazza)Bad Variable NamesSlide 27Bad variable names!Better variable names!InsertBest vs. Worst CaseSlide 32Slide 33SortSlide 35Some Algebra to calculate: 1+2+…+nSlide 37Slide 38How long does it take you to read Piazza posts and check your email and shower?Exponential RuntimeSlide 41Slide 42Logarithmic RuntimeNumber Guessing GameSlide 45// Take the log of both sidesLog2(N)Asymptotic CostSlide 49Slide 50Formal definitionWhich is fastest after some big value N?Important Big-Oh SetsWhich is fastest after some value N?Slide 55Simplifying stuff is importantWrite sum-up-to to generate an iterative process!CS61A Lecture 62011-06-28Colleen LewisClicker Test How often do you read piazza posts?A)Whenever I receive an emailB)Once or twice a dayC)When I have a questionCurrent average response time: 6 minutes!How long does a function take to run?•It depends on what computer it is run on!Assumptions•We want something independent of the speed of the computer•We typically use N which is some reference to the “size” of the data. –It might be the variable N (in factorial) –It might be the size of your sentence•We don’t care about constant factors–This is pretty silly in some cases but makes the math more beautiful•We typically think about the worst case!•It only matters for BIG input!Colleen’s Morning Routine•Eat breakfast (10 minutes)•Brush teeth (5 minutes)•Go swimming •Read Piazza (0 minutes – ???)Takes a consistent or “constant” amount of timeDepends “linearly” upon the number of laps LDepends upon the number of posts P and the words per post WConstant RuntimeO(1)Constant Runtime•The runtime doesn’t depend upon the “size” of the input(define (square x) (* x x))(define (average a b)(/ (+ a b) 2))(define (max val1 val2)(if (> val1 val2) val1 val2))DemoAssumptions•We want something independent of the speed of the computer•We typically use N which is some reference to the “size” of the data. –It might be the variable N (in factorial) –It might be the size of your sentence•We don’t care about constant factors–This is pretty silly in some cases but makes the math more beautiful•We typically think about the worst case!•It only matters for BIG input!Write a constant runtime procedure?(Brushing your teeth)Linear RuntimeO(N)Linear Runtime•The runtime DOES depend upon the “size” of the input – but just with a linear relationship (define (sum-up-to x) (if (< x 0)0(+ x (sum-up-to (- x 1)))))(define (count sent)(if (empty? sent)sent(+ 1 (count (bf sent)))))DemoAssumptions•We want something independent of the speed of the computer•We typically use N which is some reference to the “size” of the data. –It might be the variable N (in factorial) –It might be the size of your sentence•We don’t care about constant factors–This is pretty silly in some cases but makes the math more beautiful•We typically think about the worst case!•It only matters for BIG input!Write a linear runtime procedure?(Swimming laps)What is the runtime of this? (define (factorial n) (if (= n 0) 1 (* n (factorial (- n 1)))))A)Constant runtimeB)Linear runtimeC)Linear*Linear (quadratic)D)Something elseE)No clue!Correct AnswerDemoProblem Solving Tip! •THINK: Does this depend upon the “size” of the input?–Constant vs. Not Constant•Think about this for ANY function that is called!Linear * Linear (Quadratic) RuntimeO(N2)Linear * Linear Runtime (quadratic)(Reading Piazza)•The runtime DOES depend upon the “size” of the first input•For each thing in the first input, we call another linear thing(define (factorial-sent sent) (if (empty? sent) sent (se (factorial (first sent)) (factorial-sent (bf sent)))))DemoAssumptions•We want something independent of the speed of the computer•We typically use N which is some reference to the “size” of the data. –It might be the variable N (in factorial) –It might be the size of your sentence•We don’t care about constant factors–This is pretty silly in some cases but makes the math more beautiful•We typically think about the worst case!•It only matters for BIG input!Linear * Linear Runtime (quadratic)(Reading Piazza)(define (factorial-sent sent) (if (empty? sent) sent (se (factorial (first sent)) (factorial-sent (bf sent)))))Runtime:O( sent-length * value-of-elements )(define (factorial-sent sent) (if (empty? sent) sent (se (factorial (first sent)) (factorial-sent (bf sent)))))(define (square-sent sent) (if (empty? sent) sent (se (square (first sent)) (square-sent (bf sent)))))Write a linear*linear (quadratic) runtime procedure?(Reading Piazza)Bad Variable Names(Slight break from runtimes)What is the runtime of this? (define (mystery a b) (cond ((empty? b) (se a b))((< a (first b)) (se a b))(else (se (first b) (mystery a (bf b))))))A) Constant runtimeB) Linear runtimeC) Linear*Linear (quadratic)D) Something elseE) No clueCorrect Answer•Try to guess what type of thing the variables a & b will be•Try to come up with (small) input that triggers each caseBad variable names!•Make your code harder to read!–Don’t do this!•Even though we do–We will use bad variable names on exams so that you have to read/understand the codeBetter variable names! (define (insert num sent) (cond ((empty? sent) (se num sent))((< num (first sent)) (se num sent))(else (se (first sent) (insert num (bf sent))))))STk>(insert 7 ’())()STk>(insert 1 ’(2 5 8))(1 2 5 8)Insert STk>(insert 8 ’(2 5 6 9))(2 5 6 8 9)(se 8 ’(9)) (insert 8 ’(2 5 6 9))(se 2 (insert 8 ’(5 6 9))(se 5 (insert 8 ’(6 9))(se 6 (insert 8 ’(9))(se 2 (se 5 (se 6 (se 8 ’(9)))))Best vs. Worst Case(define (insert num sent) (cond ((empty? sent) (se num sent))((< num (first sent)) (se num sent))(else (se (first sent) (insert num (bf sent))))))STk>(insert 1 ’(2 3 4 5 6 7 8))(1 2 3 4 5 6 7 8)STk>(insert 9 ’(2 3 4 5 6 7 8))(2 3 4
View Full Document
Unlocking...