疑问:时间复杂度与空间复杂度的乘积是定值吗?
例如一个算法的时间复杂度是 O(N^2)
,空间复杂度是 O(1)
。优化之后,时间复杂度是 O(N)
,空间复杂度是 O(N)
,即空间换时间。
似乎二者乘积是固定的,只是牺牲一个换取另一个,总体复杂度并没有降低。算法的威力在哪里?
算法之威,深不可测。
20230308 新学动态规划,用入门的“计算斐波那契数列”问题做测试,写了三个程序: 第一个是基础的简单递归,第二个是从上至下的存储中间值,第三个是从下至上的动态规划。
斐波那契数列第 0 项是 0 , 第 1 项是 1 ,从第 2 项开始每项等于前面两项的和。
|
|
计算第 100 个斐波那契数(354224848179261915075), 动态规划用时几微秒,存储中间值用时几十到几百微秒,而简单递归计算不出来(不知何时)。
须知动态规划免去了存储过程,即空间复杂度是 O(1),而时间复杂度相较于存储中间值占优,总体复杂度都降低了,而且对比显著。
算法之威,吾当敬畏。