含分支的幂运算递归代码时间复杂度咨询：新增分支是否改变复杂度

首先明确两段代码的实现：

第一段（含奇偶分支的优化版本） #

def p(a, b):
    if b == 0:
        return 1
    elif b % 2 == 0:
        res = p(a, b // 2)
        return res * res
    else:
        return a * p(a, b - 1)

第二段（仅线性递归版本，时间复杂度O(n)） #

def p(a, b):
    if b == 0:
        return 1
    else:
        return a * p(a, b - 1)

时间复杂度变化分析 #

答案是时间复杂度发生了显著变化，从原来的O(n)降到了O(log n)。

具体原因：

• 第二段代码的逻辑是每递归一次就将b减1，直到b=0，总共需要b次递归调用，属于线性时间复杂度O(b)（即你所说的O(n)）。
• 第一段代码新增的奇数分支，本质是把奇数场景转化为偶数后进入分治逻辑：
  • 当b为偶数时，递归参数变为b//2，问题规模直接减半；
  • 当b为奇数时，仅需多一次递归将b转为偶数（b-1），随后立刻进入偶数分支的分治流程。

举个实际例子，计算p(a,7)的递归流程：

1. 7是奇数 → 调用a*p(a,6)
2. 6是偶数 → 调用p(a,3)*p(a,3)
3. 3是奇数 → 调用a*p(a,2)
4. 2是偶数 → 调用p(a,1)*p(a,1)
5. 1是奇数 → 调用a*p(a,0)
6. p(a,0)返回1

整个过程的调用次数是O(log b)级别——偶数分支的规模减半逻辑主导了复杂度，奇数场景仅增加常数次调用，不会影响整体的对数级趋势。

简言之，新增奇数分支后，代码从线性递归升级为分治递归，时间复杂度从O(n)优化到了O(log n)。

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