java - 为什么二次时间算法比线性时间算法执行得更快

Question

这里有两种不同的解决方案，用于查找“乘积小于 K 的子数组的数量”，一种运行时间为 O(n)，另一种为 O(n^2)。但是，具有 O(n^2) 的执行速度比具有线性运行时复杂度的执行速度快大约 4 倍(1 秒对 4 秒)。有人可以解释为什么会这样吗？

O(n) 运行时间的解决方案 1:

static long countProductsLessThanK(int[] numbers, int k)
{
    if (k <= 1) { return 0; }

    int prod = 1;
    int count = 0;

    for (int right = 0, left = 0; right < numbers.length; right++) {
        prod *= numbers[right];

        while (prod >= k)
            prod /= numbers[left++];

        count += (right-left)+1;
    }

    return count;
}

O(n^2) 运行时间的解决方案 2:

static long countProductsLessThanK(int[] numbers, int k) {
    long count = 0;

    for (int i = 0; i < numbers.length; i++) {
        int productSoFar = 1;

        for (int j = i; j < numbers.length; j++) {
            productSoFar *= numbers[j];

            if (productSoFar >= k)
                break;

            count++;
        }
    }

    return count;
}

示例主程序:

public static void main(String[] args) {
    int size = 300000000;
    int[] numbers = new int[size];
    int bound = 1000;
    int k = bound/2;

    for (int i = 0; i < size; i++)
        numbers[i] = (new Random().nextInt(bound)+2);

    long start = System.currentTimeMillis();
    System.out.println(countProductLessThanK(numbers, k));
    System.out.println("O(n) took " + ((System.currentTimeMillis() - start)/1000) + "s");



    start = System.currentTimeMillis();
    System.out.println(countMyWay(numbers, k));
    System.out.println("O(n^2) took " + ((System.currentTimeMillis() - start)/1000) + "s");
}

编辑1:

我在示例测试程序中选择的数组大小有 300,000,000 个元素。

编辑2:

数组大小:300000000:

O(n) 花费了 4152ms

O(n^2) 耗时 1486 毫秒

数组大小:100000000:

O(n) 耗时 1505ms

O(n^2) 花了 480 毫秒

数组大小:10000:

O(n) 耗时 2 毫秒

O(n^2) 耗时 0 毫秒

Answer 1

您选择的数字均匀分布在 [2, 1001] 范围内，并且您计算的是乘积小于 500 的子数组。找到大子数组的概率基本上为 0；其乘积小于 500 的最长可能子数组的长度为 8，并且只有九个可能的子数组具有该长度(全部为 2，以及八个包含七个 2 和一个 3 的数组)；击中其中一个的可能性微乎其微。一半的数组值已经超过 500；在给定起点找到长度为 2 的子数组的概率小于四分之一。

因此，您的理论上 O(n²) 算法与此测试实际上是线性的。而你的 O(n) 算法需要在每个点进行除法，这真的很慢； n 的小值比 n 乘法慢。