Class Notes
(806,815)

United States
(312,228)

Computer Science
(355)

COMPSCI 61A
(130)

De Nero
(43)

Lecture 18

# CS61A Lecture 18: Orders of Growth

Unlock Document

University of California - Berkeley

Computer Science

COMPSCI 61A

De Nero

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