计算2^n的递归函数时间复杂度分析求助：O(log n)还是O(n)？

先看函数代码：

unsigned long pot2_1(unsigned n)
{
    if (n==0) return 1;
    if (n%2==0) return pot2_1( n/2 ) * pot2_1( n/2 );
    else return 2 * pot2_1( n/2 ) * pot2_1( n/2 );
}

核心执行逻辑 #

这个函数的关键问题是每次递归都会重复调用两次完全相同的子问题：

• 当n=0时直接返回1，属于基准情况，时间开销为O(1)
• 当n不为0时，无论奇偶，都会两次调用pot2_1(n/2)，后续的乘法操作是常数时间开销

时间复杂度推导 #

设T(n)为计算pot2_1(n)的时间开销，递推关系如下：

• T(0) = O(1)
• 当n>0时，T(n) = 2*T(⌊n/2⌋) + O(1)

用主定理求解该递推式：

• 子问题数量a=2，子问题规模缩小比例b=2，因此log_b a = log₂2 = 1
• 额外开销f(n)=O(1)，满足f(n) = O(n^(1-ε))（取ε=1即可），符合主定理第一种情况

最终可得T(n) = Θ(n)，即该函数的时间复杂度为O(n)

为什么不是O(logn)？ #

标准快速幂算法只会递归调用一次子问题，递推式为T(n)=T(n/2)+O(1)，时间复杂度才是O(logn)。而这个函数每次都重复计算同一个子问题，相当于把工作量直接翻倍，最终导致时间开销和n成线性关系。

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