【数学】组合数学

def fib(n):
    if n==0 or n==1:
        return n
    else:
        return fib(n-2)+fib(n-1)
def count(f):
    def counted(n):
        counted.call_count +=1
        return f(n)
    counted.call_count = 0
    return counted
def memo(f):
    cache={}
    def memoized(n):
        if n not in cache:
            cache[n] = f(n)
        return cache[n]
    return memoized
fib = count(fib)
counted_fib =fib
fib = memo(fib)
fib = count(fib)
print(fib(30))
print("origin:", fib.call_count, "memorized:", counted_fib.call_count)

832040
origin: 59 memorized: 31

Exponentiation

优化指数运算至\(o(\log n)\)
以下显示了进行优化后的算法在不同数据量下的运行时间图，呈现对数曲线趋势

%matplotlib inline
import matplotlib.pyplot as plt
plt.style.use('ggplot')
plt.rc('font', size = 16)

from timeit import repeat
from numpy import median, percentile

def plot_times(name, xs, n=15):
    f = lambda x: name+'('+str(x)+')'
    g = globals()

    samples = []
    for _ in range(n):
        times = lambda x: repeat(f(x), globals = g, number = 1, repeat = n)
        samples.append([median(times(x)) for x in xs])
    ys = [10e3*median(sample) for sample in zip(*samples)]

    plt.figure(figsize=(8, 8))
    plt.plot(xs, ys)
    plt.xlabel('n')
    plt.ylabel('ms')

def exp_fast(b,n):
    if n==0:
        return 1
    elif n%2==0:
        return square(exp_fast(b,n//2))
    else:
        return b*exp_fast(b, n-1)

def square(x):
    return x*x

exp_2_fast = lambda n: exp_fast(2.0, n)
plot_times('exp_2_fast', range(20, 1600, 10))

Order of Growth Notation

时间复杂度常用大O与大\(\Theta\)表示法表示
- 大O描述了运行时间上限 - 大\(\Theta\)则对同时表示了上限与下限常见的时间复杂度表示（大O与大\(\Theta\)自行替换符号）： - 指数增长：\(o(b^n)\) - 二次增长：\(o(b^2)\) - 线性增长：\(o(n)\) - 对数增长：\(o(\log n)\) - 常数增长：\(o(1)\)

Space

Active environment: - 正在被调用的函数的环境 - 函数的父函数在活动环境中（即嵌套函数内层调用时） python会自动检测非活动环境并将其回收

【CS61A】CS61A——Composition

发表于 2025-05-18 更新于 2025-07-31 分类于 CS61A
本文字数： 2.5k 阅读时长 ≈ 5 分钟

Composition

Linked List

用Python实现链表 - 每个节点由first与rest组成，前者表示值，后者表示链接的剩余链表 - 将每个节点当作一堆二元组看待 - 最后一个节点指向空链表Link.empty，使用类属性表示 - 构造方式：Link(3, Link(4, Link(5, Link.empty))) ### 创建链表

class Link:
    # 使用空元组实现空节点，类属性
    empty = ()
    def __init__(self, first, rest=empty):
        # 判断rest是否是空节点或是一个Link类
        assert rest is Link.empty or isinstance(rest, Link)
        self.first = first
        self.rest = rest


s = Link(3, Link(4, Link(5)))
print(s.first)
print(s.rest.first)
print(s.rest.rest.first)
print(s.rest.rest.rest is Link.empty)

操作列表

实现如下行为：range, map, filter 我们使用递归实现

class Link:
    # 使用空元组实现空节点，类属性
    empty = ()
    def __init__(self, first, rest=empty):
        # 判断rest是否是空节点或是一个Link类
        assert rest is Link.empty or isinstance(rest, Link)
        self.first = first
        self.rest = rest
def range_link(start, end):
    if start>=end:
        return Link.empty
    else:
        return Link(start, range_link(start+1, end))

def map_link(f, s):
    if s is Link.empty:
        return s
    else:
        return Link(f(s.first), map_link(f, s.rest))

def filter_link(f, s):
    if s is Link.empty:
        return s
    filter_rest = filter(f, s.rest)
    if f(s.first):
        return Link(s.first, filter_rest)
    else:
        return filter_rest

链表的改变

可以通过对属性赋值来改变链表的first和rest属性

>>> s = Link(1, Link(2, Link(3)))
>>> s.first = 5
>>> t = s.rest
>>> t.rest = s;
>>> s.first
5
>>> s.rest.rest.rest.rest.rest.first
2

此赋值将s的后段与前段相接，创建了一个循环链表

插入节点

向一个有序链表中添加节点，保证链表仍有序

def add(s, v):
    assert s is not Link.empty
    if s.first > v:
        s.first, s.rest = v, Link(s.first, s.rest)
    elif s.first < v and s.rest is Link.empty:
        s.rest = Link(v)
    elif s.first < v:
        add(s.rest, v)
    return s

Tree Class

使用类实现树 ### 创建树

class Tree:
    def __init__(self, label, branches = []):
        self.label = label
        for branch in branches:
            assert isinstance(branch, Tree)
        self.branches = list(branches)
    def __repr__(self):
        if self.branches:
            branches_str = ', '+ repr(self.branches)
        else:
            branch_str = ''
        return 'Tree({0}{1})'.format(repr(self.label), branch_str)
    def __str__(self):
        return '\n'.join(self.indented())

    def indented(self):
        lines = []
        for b in self.branches:
            for line in b.indented():
                lines.append('    '+line)
        return [str(self.label)] + lines
    def is_leaf(self):
        return not self.branches

实现一些操作

如下代码实现了创建斐波那契树以及输出叶子节点

def fib_tree(n):
    if n==0 or n==1:
        return Tree(n)
    else:
        left = fib_tree(n-2)
        right = fib_tree(n-1)
        fib_n = left.label + right.label
        return Tree(fib_n, [left, right])

def leaves(t):
    if t.is_leaf():
        return [t.label]
    else:
        all_leaves = []
        for b in t.branches:
            all_leaves.extend(leaves(b))
        return all_leaves

剪枝

# 通过每次重新构建branches列表，将等于n的值排除在列表外以实现
def prune(t, n):
    t.branches = [b for b in t.branches if b.label!=n]
    for b in t.branches:
        prune(b, n)