CS61A Lecture 18: Orders of Growth

3 Pages
Unlock Document

University of California - Berkeley
Computer Science
De Nero

Memoization Idea: Remember the results that have been computed before def memo(f): """Return a memoized version of single-argument function f. >>> big_fib_tree = fib_tree(35) >>> big_fib_tree.entry 5702887 >>> big_fib_tree.left is big_fib_tree.right.right True >>> sum_entries(big_fib_tree) 142587180 >>> count_entries(big_fib_tree) 18454929 """ cache = {} def memoized(n): if n not in cache: cache[n] = f(n) return cache[n] return memoized Use @memo decorator to reduce calculation times for functions (ex. Fib) with repeated structures Stores data that have been computed in cache Hog Strategy with Tree Recursion Chance of winning game when score is S to T is: max: Your chance of winning game by rolling N dice sum: Probability of scoring K points in N rolls * (1 - Opp Chance of winning game after score K) New score is (T, S+K) or (S+K, T) Time Implementation of same functional abstraction require different amounts of time to compute result Problem: How many factors does positive integer n have? A factor k of n is a positive integer such that n/k is also a positive integer Slow: Test each k from 1 through n Fast: Test each k, from 1 to square root n, for every k, n/k is also factor def count_factors_fast(n): """Count the positive integers that evenly divide n. >>> count_
More Less

Related notes for COMPSCI 61A

Log In


Don't have an account?

Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Sign up

Join to view


By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.

Add your courses

Get notes from the top students in your class.