递归递增函数最坏时间复杂度疑问：O(logn)还是O(1)

你的分析是正确的，该函数的最坏情况时间复杂度为O(log n)，老师的结论有误，具体解释如下：

1. 最坏情况的执行流程 #

对于形如2ⁿ - 1的输入（比如7、15、31等），函数会触发连续的递归调用：

• 输入7：7→3→1→0，共3次递归调用
• 输入15：15→7→3→1→0，共4次递归调用

这类输入的二进制全为1，每次递归都会执行floor(x/2)（相当于二进制右移一位），直到x变为0（偶数）才停止。递归调用的次数等于输入x的二进制位数，也就是log₂(x+1)，对应量级为O(log n)。

2. 老师结论的误区 #

老师混淆了单个操作的时间复杂度和整体算法的时间复杂度：

• 函数里的取模x%2、除法floor(x/2)、乘法2*...确实都是常数时间（O(1)）操作
• 但整体时间复杂度由操作的总次数决定，最坏情况下操作次数随输入x的对数增长，因此整体复杂度是O(log n)，而非O(1)

3. 代码执行验证 #

以输入7为例，函数的调用链展开后是：

function(7) = 2*function(3)
function(3) = 2*function(1)
function(1) = 2*function(0)
function(0) = 0+1 = 1

最终计算需要3次递归调用，每次调用对应O(1)的操作，总操作次数与log₂(7)成正比。

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