java - 如何确定对整数数组进行合并排序的可能运行时间？

Question

我正在测试我的一些排序算法的运行时间，我在一个大小为 1,280,000 的数组上测试了这个算法，得到的运行时间约为 0.246 秒。我现在正试图计算出我的算法在双倍大小 (2,560,000) 的数组上的理论运行时间。我想弄清楚如何根据合并排序的大 O 计算运行时间，即 nlog(n)。我将 .246 插入到 nlogn 算法中，但得到了一个负数。 Google 和其他堆栈溢出问题并没有完全帮助。我的 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

在“理论”中，归并排序是一种复杂度为O(n.log(n))的算法。
这是一个我们都知道的事实，但是:实际上，许多因素对我们不利，对我们有利。即内存限制、CPU 过载以及您的情况下的 Java 堆。

假设您已经在一台没有边界的机器上运行了您的代码:

=

0.246 = alpha * n * log(n)
where n=1,280,000 and alpha is our machine process factor

0.246 = alpha * 1.28E+6 * log(1.28E6) --> alpha = 0.246/(1.28E6*log(1.28E6)) --> alpha = 3.14689524e-8

现在让我们用计算出的 alpha 和 n=2,560,000 替换数字:

estimate = 3.14689524e-8 * 2.56E6 * log(2.56E6) --> estimate = 0.51625113199

所以大约需要 0.516 秒。

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