1

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

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

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

我有一个 shell 排序的实现：

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;
     }
}
}

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

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

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

但是，当我使用 gap = 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));
    }
}
4

1 回答 1

2

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

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

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

于 2013-05-16T05:43:58.373 回答