例如一个算法的时间复杂度是 $O(N^2)$，空间复杂度是 $O(1)$。 优化之后，时间复杂度是 $O(N)$，空间复杂度是 $O(N)$，即空间换时间。 似乎二者乘积是固定的，只是牺牲一个换取另一个，总体复杂度并没有降低。 算法的威力在哪里？

2023-03-08 新学动态规划，用入门的「计算斐波那契数列」问题做测试，写了三个程序： 第一个是基础的简单递归，第二个是从上至下的存储中间值，第三个是从下至上的动态规划。

斐波那契数列第 0 项是 0 ， 第 1 项是 1 ，从第 2 项开始每项等于前面两项的和。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

# assuming n is a none-negative integer

def f1(n):
    if n <= 1:
        return n
    return f1(n-1) + f1(n-2)

tab = {0:0, 1:1}
def f2(n):
    if n not in tab:
        tab[n] = f2(n-1) + f2(n-2)
    return tab[n]

def f3(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a+b
    return a

计算第 100 个斐波那契数（354224848179261915075）， 动态规划用时几微秒，存储中间值用时几十到几百微秒，而简单递归计算不出来。 须知动态规划没有额外存储，空间复杂度是 $O(1)$；计算速度快过存储中间值，时间复杂度也占优。 也就是说总体复杂度都降低了。

这便回答了开头的疑问，时间复杂度与空间复杂度并非此消彼长，而是可以被优良的算法同时降低。 算法本质上是将复杂度转移到工程实现上，这在实践中十分常见。 用工程复杂度换取时间/空间复杂度，这便是算法的威力。 当然，信息论指出降低复杂度有一个限度，这是算法无法逾越的鸿沟。