java - 为什么我在这两个不同的嵌套 for 循环中得到不同的时间复杂度？

Question

好的，所以我知道两个嵌套的 for 循环每个递增 1 给出二次时间复杂度。然后我很好奇，如果我更改其中一个循环的更新(递增 2)，我会得到 O(n log n) 而不是 O(n^2)，反之亦然，另一个循环也如此。

在每个内部循环中，我都有一个变量来计算循环执行的次数。该数组的大小为 2^20，即 1,048,576。我认为这两种方法应该具有相同的复杂度 n log n (20 * 1,048,576)。但只有算法 2 接近该复杂度，而算法 1 的复杂度为 n * 2。

据我了解，一个循环的复杂度是 O(n)，另一个循环的复杂度是 O(log n)，所以它在一起应该是 O(n log n)，然后如果我切换它们，我应该得到 O(log n n) 的复杂度这将是同样的事情。

 int[] arr = new int[1048576];

    // Algorithm 1
    int counter1 = 0;
    for (int i = 1; i < arr.length; i++) {
        for (int j = i; j < arr.length; j *= 2) {
            counter1++;
        }
    }
    System.out.println(counter1);

    // Algorithm 2
    int counter2 = 0;
    for (int i = 1; i < arr.length; i *= 2) {
        for (int j = i; j < arr.length; j++) {
            counter2++;
        }
    }
    System.out.println(counter2);

    // counter1: 2097130 (n * 2)
    // counter2: 19922945 (n log n)

Answer 1

简单的数学。现在假设 w *= 2 基本上需要 20 个步骤才能达到大约 100 万。

算法 1 将运行大约 100 万个 j 循环，但每个循环只需要大约 20 个 j 步即可完成。您在算法 2 上运行内部循环(尤其是第一次)的次数为数百万次，而另一个将运行 <=20 次，即 100 万次。 但是，您需要考虑衰减，尤其是在开始时。当您点击 i=2 时，算法的 j 步数已经减少到了 19 个。到了 4 岁，你就降到了 18 岁，依此类推。这种早期衰减本质上会“扼杀”步数的动量。最后约 500,000 个“i-steps”只会使计数器增加一次。

算法 2 在第一次单独运行时运行 100 万个 j 步，然后是另一个 (i-step-1) j 步(1，然后是 2，然后是 4，等等)。您每次大约跑一百万步。