如何确定INT数组上合并排序的可能运行时间？

Question

我正在测试一些排序算法的运行时间，我在一个1280000大小的数组上测试了这个算法，得到了大约0.246秒的运行时间。我现在试图计算出我的算法在两倍大小（2560000）的数组上的理论运行时间。我试图找出如何基于合并排序的big-O计算运行时间，即nlog（n）。我在nlogn算法中插入了.246，但得到了一个负数。谷歌和其他堆栈溢出问题并没有完全起到帮助作用。我的mergeSort工作正常，但我在下面附上了它的代码。感谢您的帮助，提前感谢！

/**
 * This is another sorting algorithm where the data array is first split
 * into two, then recursively sorted, at each recursive level the method
 * will merge the current two variables together, and by the time the method
 * reaches the root call the array will be sorted.
 * @param data: The array that needs to be sorted.
 * @param first: The starting index of the sort.
 * @param n : The ending index of the sort.
 */
public static void mergeSort(int[] data, int first, int n) {

    if (data.length < 2) {
        return;
    }
    int n1;//first element of first half
    int n2;//first element of the second half
    if (n > 1) {
        //figure out the size of the array
        n1 = n / 2;
        n2 = n - n1;

        mergeSort(data, first, n1);
        mergeSort(data, first + n1, n2);

        //now merge the two halves
        merge(data, first, n1, n2);
    }

}

private static void merge(int[] data, int first, int n1, int n2) {
    int[] temp = new int[n1 + n2];
    int copied = 0;
    int copied1 = 0;
    int copied2 = 0;
    int i;

    while ((copied1 < n1) && (copied2 < n2)) {
        if (data[first + copied1] < data[first + n1 + copied2]) {
            temp[copied++] = data[first + (copied1++)];
        } else {
            temp[copied++] = data[first + n1 + (copied2++)];
        }
    }
    //make sure copied1 is completely transferred over
    while (copied1 < n1) {
        temp[copied++] = data[first + (copied1++)];
    }
    //copy temp into data to complete the process
    for (i = 0; i < copied; i++) {
        data[first + i] = temp[i];
    }

}

Answer 1

您的测试规模非常小。

您需要多次重复您的实验，并使用许多不同的大小，以便您可以绘制不同时间消耗图的图。

原因：在物理处理器上，机器使用缓存：快速内存，因此处理器得到最佳使用。程序完全加载到缓存中需要一段时间。

这意味着，第一次运行程序时，需要花费更多的时间，因为加载程序时浪费了部分时间。这叫做冷启动。第二次，可以从上一次运行之前执行的工作中受益。这叫做热启动。

此外，运行时间往往也取决于外部因素。假设你运行了这个程序，但同时网络上发生了一些事情，或者你插入了一个USB设备。在这种情况下，操作系统将暂停执行，并首先对事件进行一些簿记。簿记可以运行到毫秒，因此对单次运行有重大影响。

此外，您需要尝试不同的阵列。排序的数组通常比未排序的数组排序更快。这是因为许多合并实现使用交换（以提高性能），从而执行较少的交换。

震荡：你应该使用不同的数组，不同的大小，并经常重复这个实验，以平衡缓存等方面。

如果您这样做了，您可以如下确定运行时间。由于时间复杂度为O（n logn），这意味着函数采用以下形式：

a*n log n+b*n+c*log n+d

您可以将此公式插入最小二乘方法的Vandermonde矩阵中：

[  1    log(n_1)    n_1    n_1*log(n_1)  ]                 [ t_1 ]
[  1    log(n_2)    n_2    n_1*log(n_2)  ]      [ d ]      [ t_2 ]
[  1    log(n_3)    n_3    n_1*log(n_3)  ]      [ c ]      [ t_3 ]
[  1    log(n_4)    n_4    n_1*log(n_4)  ]   x  [ b ]  =   [ t_4 ]
[  1    log(n_5)    n_5    n_1*log(n_5)  ]      [ a ]      [ t_5 ]
[  1      ...       ...        ...       ]                 [ ... ]
[  1    log(n_m)    n_m    n_1*log(n_m)  ]                 [ t_m ]

或者用矩阵表示法：

X * w = t

使用n_i实验的数组大小i和t_i排序此数组所需的时间。

然后，您可以通过计算以下各项来确定常数：

w = (X^T*X)^-1*X*t

例如，您可以使用GNU/Octave执行此操作。

然后，您可以使用最小二乘法导出a、b、c和d。这应该给出一个很好的时间近似值。

如果它们差异太大，则说明您的实现有问题。如果a为（接近）零，则您的算法可能表现为sub O（n log n），并且如果函数跟不上数据点，则行为更强（因此O（n^2））

Answer 2

在“理论”中，合并排序是一种复杂度为O（n.log（n））的算法<这是我们都知道的事实，但事实上，许多因素对我们不利，对我们有利。i、 e.内存限制、CPU过载以及Java堆。

=

0.246=alpha*n*log（n）
其中n=1,280,000，alpha是我们的机器过程因子

0.246=alpha*1.28E 6*log（1.28E6）--

现在让我们用计算出的alpha替换数字，n=2560000：

估计值=3.14689524e-8*2.56E6*log（2.56E6）--

所以大约需要0.516秒。

注意：这仅在您拥有无限资源且没有后台进程时有效。