Class Notes (806,815)
United States (312,228)
COMPSCI 61A (130)
De Nero (43)
Lecture 18

# CS61A Lecture 18: Orders of Growth

3 Pages
109 Views

School
University of California - Berkeley
Department
Computer Science
Course
COMPSCI 61A
Professor
De Nero
Semester
Fall

Description
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

OR

Don't have an account?

Join OneClass

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

Join to view

OR

By registering, I agree to the Terms and Privacy Policies
Just a few more details

So we can recommend you notes for your school.