关于方法f6时间复杂度的疑问：测试为何显示为常数时间？

我需要分析下面这个Java方法f6的时间复杂度，原本以为整体是O(n·2ⁿ)——外层循环运行n次，内层循环的k每次翻倍，运行次数对应2ᵏ。但用System.nanoTime测试后发现，数据规模增大时耗时始终保持恒定。我不确定自己的判断是否正确，如果该方法实际是常数时间复杂度，请解释原因。

方法代码 #

public static void f6(int n) {
    int k = 1, a = 0;
    for(int i = 0; i < n; i += 1) {
        for(int j = 0; j <= k * 2; j += 1) {
            a = i + j;
        }
        k = k * 2;
    }
}

测试说明 #

• 左列：函数名
• 中列：数据量
• 右列：耗时

分析与解释 #

1. 理论时间复杂度的正确计算 #

你之前的时间复杂度计算有误：外层循环执行n次，第i次迭代（i从0开始）时，k的值是2ⁱ，内层循环的终止条件是j <= k*2，因此内层循环的执行次数是k*2 + 1 = 2ⁱ⁺¹ + 1。

总操作次数为：
$$
\sum_{i=0}^{n-1} (2^{i+1} + 1) = 2*(2^n - 1) + n = 2^{n+1} + n - 2
$$
因此理论时间复杂度是O(2ⁿ)，而非O(n·2ⁿ)。

2. 测试耗时恒定的原因 #

Java中int是32位有符号整数，最大值为2³¹-1。当i增加到30时，k = 2³⁰，此时k*2 = 2³¹，超过int的最大值，发生整数溢出，结果变为负数（有符号整数溢出后按补码规则循环）。

此时内层循环的条件j <= 负数，而j从0开始，循环体直接不会执行。当i≥31时，k会继续翻倍，结果始终是负数或0，内层循环都不会运行。

也就是说，当n超过30之后，外层循环的后续迭代根本不会执行任何内层循环操作，总操作次数不再随n增大而增加，因此测试时耗时始终恒定。

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