循环内自调用的递归函数时间复杂度求解及疑问解答

首先给出待分析的函数代码：

void function(n) 
{        
    for (int i = n; i > 0; i = floor(i/2))
    {            
        function(floor(i/2));
    }               
}

递推式推导 #

定义T(n)为function(n)的时间复杂度，其中T(0)=O(1)（输入为0时循环不执行，直接返回）。

当n≥1时，函数内的循环会执行**⌊log₂n⌋+1**次（每次i减半，直到i≤0），每次循环中调用function(floor(i/2))，因此递推式为：
T(n) = T(⌊n/2⌋) + T(⌊n/4⌋) + T(⌊n/8⌋) + ... + T(0) + O(log n)

简化递推（n为2的幂的情况） #

假设n是2的幂，令n=2^m（m为非负整数），则递推式可转换为：
T(2^m) = T(2^(m-1)) + T(2^(m-2)) + ... + T(2^0) + T(0) + O(m)

对比T(2^(m-1))的表达式：
T(2^(m-1)) = T(2^(m-2)) + ... + T(2^0) + T(0) + O(m-1)

将T(2^(m-1))代入T(2^m)的表达式，化简后得到更简洁的递推关系：
T(2^m) = 2 * T(2^(m-1)) + O(1)

求解递推式 #

针对简化后的递推式T(2^m) = 2*T(2^(m-1)) + C（C为常数），结合初始条件T(1)=O(1)（当n=1时，循环执行1次，调用function(0)，总操作数为常数）：

1. 构造等比数列：令S(m) = T(2^m) + C，则S(m) = 2*S(m-1)，这是公比为2的等比数列
2. 解得S(m) = S(0)*2^m，代入S(0)=T(1)+C=O(1)，可得T(2^m)=O(2^m)
3. 由于n=2^m，即m=log₂n，因此T(n)=O(n)

非2的幂的情况验证 #

对于任意正整数n，T(n)的增长速度与相邻的2的幂的T值一致（例如T(3)=T(2)=O(2)，T(5)=T(4)=O(4)），因此整体时间复杂度仍为O(n)。

内容的提问来源于stack exchange，提问作者Лука