java - Java 中数组排序的时间如何根据间隙大小发生显着变化？

Question

我基本上根据大小创建 10 个随机数组: 8000,16000,32000,64000,128000,256000

我的意思是我有 10 个大小为 8000 的数组，10 个大小为 16000 的数组，等等。

这些都填充了从 0 到数组大小的随机数。

我有一个希尔排序的实现:

public static void sortMyArray(int[] a){
for (int gap = a.length / 2; gap > 0; gap = (gap / 2)) {
    for (int i = gap; i < a.length; i++) {
        int tmp = a[i];
        int j = i;
        for (; j >= gap && tmp < (a[j - gap]); j -= gap) {
            a[j] = a[j - gap];
        }
        a[j] = tmp;
     }
}
}

当间隙为gap = a.length/a.时length 我只是有一个插入排序。以下是对这些数组进行排序的时间:

Number of Elements  Milliseconds
8000                13
16000               53
32000               217
64000               828
128000              3311
256000              13352

所以这大约是 O(N^2)。当元素数量加倍时，求解时间几乎增加 4 倍。

但是，当我使用间隙 = a.length/2 时，我得到如下值:

Number of Elements  Milliseconds
8000                2
16000               2
32000               4
64000               10
128000              25
256000              60

所以我猜这比 O(N) 更好？ 这怎么可能？我尝试从 Windows 关闭处理器，并尝试仅在 1 个处理器上运行计算机，但这些值仍然不符合逻辑。

如果您有兴趣，这是我的完整代码:

int[] arraySizes = new int[]{8000,16000,32000,64000,128000,256000};
Random rn = new Random(1);

for(int i=0;i<arraySizes.length;i++){
    int[] arrayToBeSorted = new int[arraySizes[i]];
    System.out.println("Solving array with: " + arraySizes[i] + " elements with first sorting algorithm.");
    for (int c = 0; c < 10; c++) {
        for(int t=0;t<arraySizes[i];t++){
            int randomNumber = rn.nextInt(arrayToBeSorted.length);
            arrayToBeSorted[t] = randomNumber;
        }
        Long initialTime = (new Date().getTime());
        sortMyArray(arrayToBeSorted);
        Long finalTime = (new Date().getTime());
        System.out.println("Time in milliseconds:" + (finalTime - initialTime));
    }
}

Answer 1

尽管您的实现似乎是正确的，但您的假设却并非如此。

您假设如果一个函数的复杂度为 O(n^2) 且运行时间为 3311 秒，那么其他复杂度为 O(n) 的函数应该在相同的数据上运行大约 57 秒。

然而，大 O 表示法给出了函数增长率的概念，而不是实际运行时间。因此，您不能仅根据增长率来比较不同函数的运行时间。