递归函数f3的运行时间复杂度分析：O(logn)还是O(n)？

函数代码 #

int f3(int i, int j)
{
    if (i < 10)
    {
        return i;
    }
    else if (i < 100)
    {
        return f3(i - 2, j);
    }
    else
    {
        return f3(i / 2, j);
    }
}

复杂度分析 #

首先参数j未参与任何逻辑计算，不影响递归过程。我们按i的取值范围分情况讨论：

• 当i < 10时：直接返回结果，时间复杂度为O(1)。
• 当10 ≤ i < 100时：每次递归将i减2，直到i < 10。最多需要(99-9)/2 = 45次调用，属于固定常数次数，时间复杂度仍为O(1)。
• 当i ≥ 100时：每次递归将i除以2，直到i < 100。由于每次i的规模减半，这个阶段的调用次数是对数级的，具体为log₂(i) - log₂(100)，对应时间复杂度O(log i)。

结论 #

整个函数的时间复杂度由i ≥ 100的阶段主导，最终为O(log n)（其中n代表输入参数i的大小）。你的判断正确，除以2的操作让调用次数呈对数增长，而i < 100的阶段是常数级开销，不会改变整体复杂度的阶数。

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