这个方法的时间复杂度是常数吗？

Question

我的任务是找出该方法的时间复杂度，但我不确定为什么它是恒定的。 我的想法是，总体时间复杂度是 n2^n，因为外循环运行 n 次，内循环运行 2^k 次，因为 k 每次都乘以两倍外循环运行。然而，当我使用

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;
    }
}

测试左栏：函数名；中间栏：项目数量；右栏：所用时间：

Answer 1

您将

a

和

k

变量定义为整数，并且（至少是

k

变量）不能增加到 ^2 超过 32 倍。因此 JVM 知道

k = k^2

的方程仅在前 31 次有意义，并且不会进行过多的迭代。

更重要的是，如果计算后不使用结果，JVM 也可以决定不执行计算。

所以，解决方案：

1. 将

   int a,k

   更改为

   long a,k

   。
2. 使用结果（sysout 就足够了）

Answer 2

我的想法是，总体时间复杂度为 n2^n，因为外循环运行 n 次，内循环运行 2^k 次，因为每次 k 都会乘以两倍。外循环运行。

嗯，O(n2ⁿ) 肯定是方法渐近复杂度的an上限。就目前而言，您的分析是正确的。但如果你看得更深一点，你可以得到一个更紧的，但仍然具有简单的形式。

写出一些内循环迭代计数：

1  2  4  8 ...

一直到 2^n-1。所有这些的总和可以表示为 Σ_{i = 1…n} 2^i-1。如果您还不知道这一总和的结果，那么您应该了解一下。我会让你这么做。