调用x上下两半的递归函数记忆化后的时间复杂度分析

无记忆化的时间复杂度 #

无记忆化时，同一个子问题会被重复计算，时间复杂度是O(x)（等价于O(2^m)，其中m是x的二进制位数）。比如x=9时，f(2)会被多次调用；x=2^k-1这类全1二进制数时，递归树会完全展开，每个数从1到x都会被多次计算，总节点数和x成正比。

带记忆化的时间复杂度 #

加入记忆化后，每个子问题f(k)只会被计算一次，时间复杂度优化为O(logx)，原因如下：

• 递归过程中涉及的所有k，都是从x出发，通过“除以2”或“加减1后除以2”得到的数，这些数的二进制位数最多比x少log2x位；
• 即使x是奇数需要调用两个子问题，这两个子问题的后续递归路径会大量重叠（比如f((x+1)/2)和f((x-1)/2)的子问题会共享很多已缓存的结果）；
• 实际需要计算的不同k的数量和x的二进制位数成正比，也就是O(logx)级别。

举个直观例子：x=15（二进制1111），带记忆化时仅需计算f(15)、f(8)、f(7)、f(4)、f(3)、f(2)、f(1)，共7个不同的子问题，而log2(15)≈3.9，数量是logx的2倍左右，仍属于O(logx)范畴。

总结 #

• 无记忆化：时间复杂度O(x)（或O(2^m)，m为x的二进制位数）；
• 带记忆化：时间复杂度O(logx)，记忆化完全避免了子问题的重复计算，将指数级（相对于位数）的复杂度优化到了对数级。

内容的提问来源于stack exchange，提问作者MangoPizza