在简单字典树(Trie)的实现一文中，我们以单词输入自动提示为引子，简单介绍了字典树的实现。那么，字典树到底可以用于哪些场合呢？

1. 前缀匹配：给定字典库，输入一段字符，返回以该字符串为前缀的所有单词。
2. 字频统计：给出一段文本，统计其中指定单词出现的频数。

之前用python简单写了一下斐波那契数列的递归实现（如下），发现运行速度很慢。

1
2
3
4
5
6

def fib_direct(n):
    assert n > 0, 'invalid n'
    if n < 3:
        return n
    else:
        return fib_direct(n - 1) + fib_direct(n - 2)

然后大致分析了一下fib_direct(5)的递归调用过程，如下图：

可以看到多次重复调用，因此效率十分低。进一步，可以算出递归算法的时间复杂度。T(n) = T(n-1) + T(n-2)，用常系数线性齐次递推方程的解法，解出递推方程的特征根，特征根里最大的n次方就是它的时间复杂度O(1.618^n)，指数级增长。

为了避免重复调用，可以适当地做缓存，python的装饰器可以完美的完成这一任务。

首先需要搞清楚两个概念：赋值和引用，对于操作 target = source:

1. 赋值操作：程序先新建对象target，然后将source的值拷贝到target中。这里，target和source值相同，但是它们是两个完全不同的对象。

2. 引用操作：程序直接将target指向source，也就是说target和source是同一个对象，target只不过是source的一个别名。

python中没有赋值，只有引用。

1
2
3
4

>>> source = 12
>>> target = source
>>> target is source
True

如果我们想拷贝一个对象，而不仅仅是创建一个引用，那么该如何操作呢？万能的python提供了两种拷贝机制浅拷贝(shallow copy)、深拷贝(deep copy)供我们选择，浅拷贝和深拷贝的唯一区别在于对嵌套对象的拷贝处理上。