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

Question

这里有两种不同的解决方案来寻找 "Number of subarrays having product less than 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) 耗时 4152 毫秒

O(n^2) 耗时 1486 毫秒

数组大小：100000000:

O(n) 耗时 1505 毫秒

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 乘法慢

Answer 2

在第一个中，您要进行除法（慢）、乘法和多次求和。

在第二个中，较重的操作是乘法，正如第一个答案所说，该算法对于您的测试用例是有效线性的。

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

Why would a quadratic time algorithm execute faster than a linear time algorithm

java

algorithm

greedy