初识算法之威:算法复杂度

疑问:时间复杂度与空间复杂度的乘积是定值吗?

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

算法之威,深不可测。

20230308 新学动态规划,用入门的“计算斐波那契数列”问题做测试,写了三个程序: 第一个是基础的简单递归,第二个是从上至下的存储中间值,第三个是从下至上的动态规划。

斐波那契数列第 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),而时间复杂度相较于存储中间值占优,总体复杂度都降低了,而且对比显著。

算法之威,吾当敬畏。

Built with Hugo
Theme Stack designed by Jimmy