含常数时间操作的通用暴力回溯函数时间复杂度分析

问题对应代码 #

def myfunc(x,a):
    if x == a:
       return
    myfunc2() #Some constant time work
    myfunc(x+1,a)
    myfunc(x+1,a)

复杂度推导过程 #

主定理仅适用于「将原问题拆分为若干个规模等比例缩小的子问题」的分治类递归，你遇到的是参数线性递减、每次固定分支数的回溯类递归，用递归树分析法就可以直接推导，不需要套用主定理。

• 先定义递推关系：设T(k)表示当前递归距离终止条件还有k层（即k = a - x）时的总时间开销。
• 终止条件：当k=0（也就是x==a）时，函数直接返回，开销为常数，记为T(0) = O(1)。
• 递推逻辑：当k>0时，当前函数首先执行常数时间的myfunc2()，固定开销记为常数c，随后发起2个k-1层的递归调用，因此递推式为：
  T(k) = 2*T(k-1) + c

对递推式做展开求解：

T(k) = 2*T(k-1) + c
     = 2*(2*T(k-2) + c) + c = 2^2*T(k-2) + 2c + c
     = 2^3*T(k-3) + 4c + 2c + c
     ...
     = 2^k*T(0) + c*(2^0 + 2^1 + ... + 2^{k-1})

其中等比数列求和2^0 + 2^1 + ... +2^{k-1} = 2^k -1，代入后可得：
T(k) = 2^k*O(1) + c*(2^k -1) = O(2^k)

你初始调用是myfunc(0,a)，此时k=a，因此总时间复杂度为O(2^a)。

结论说明 #

• 每次递归调用里新增的固定常数时间操作，只会改变复杂度的常数项系数，不会改变指数级的复杂度量级。
• 从递归树的视角看，这段代码的执行过程等价于遍历一棵高度为a的完全二叉树：整棵树总共有2^a -1个非叶子节点、2^a个叶子节点，每个节点的执行开销都是常数，总开销和节点总数成正比，自然是O(2^a)量级。
• 你之前提到的2^(nm)是多维度枚举场景的复杂度结论，和当前单参数a的简化场景不冲突，只要每个递归节点的开销是常数，不管维度多少，总复杂度都等于递归树的总节点数量级。
• 这类参数递减、固定分支的递归复杂度推导，都可以用递归树分层求和的方法计算，属于算法复杂度分析的基础方法，比主定理的适配场景更广。

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