结合律与动态规划

February 06, 2019

自然数的乘法是在其加法的基础上递归定义的:

mN.0×m:=0\forall m \in \mathbb{N}.0 \times m := 0

假设已经定义了 n×mn\times m,那么

m,nN.(n++)×m:=(n×m)+m\forall m,n \in \mathbb{N}.(n++) \times m := (n\times m) + m

比如 4×a4 \times a 定义如下:

((((0++)++)++)++)×a((((0++)++)++)++) \times a

:=(((0++)++)++)×a+a:= (((0++)++)++) \times a + a

:=(((0++)++)×a+a)+a:= (((0++)++) \times a + a) + a

:=(((0++)×a+a)+a)+a:= (((0++) \times a + a) + a) + a

:=((((0)×a+a)+a)+a)+a:= ((((0) \times a + a) + a) + a) + a

:=(((0+a)+a)+a)+a:= (((0 + a) + a) + a) + a

:=((a+a)+a)+a:= ((a + a) + a) + a

按照定义的计算方式,需要进行 33 次加法得到 4×a4\times a

但是由于乘法具有结合律(为什么?根据 Peano 公理证明可得),

m,n,lN.(m+n)+l=m+(n+l)\forall m,n,l\in \mathbb{N}.(m+n)+l=m+(n+l)

所以有

((a+a)+a)+a((a + a) + a) + a

=(a+a)+(a+a)= (a + a) + (a + a)

我们只需要进行 22 次加法:首先计算 a+aa+a,令其为 bb,再计算 b+bb+b

同理,按定义计算 8×a8 \times a 需要 7 次,通过结合律转换后只需要 33 次即可。

(((((((a+a)+a)+a)+a)+a)+a)+a)(((((((a + a) + a) + a) + a) +a) +a) + a)

=((a+a)+(a+a))+((a+a)+(a+a))= ((a + a) + (a + a)) + ((a + a) + (a + a))

从动态规划的角度,这种新的递归方式构造出了一堆重复子问题,从而把时间复杂度从简单递归的 O(n)O(n) 减少到了 O(logn)O(\log n)。其算法的正确性来源于结合律的正确性。

感谢结合律!