algorithm - 壳牌比。希伯德时间复杂度比较

Question

我正在做一个实验来比较 Thomas Hibbard 的 shell 排序(间隙大小 = 2^k-1)和 Donald Shell 的 shell 排序(n/2^k)如何在同一个数组上执行。当数组的大小为 10 到 1000 时，Hibbard 的性能优于 shell。但是当大小达到 10000 或更高时，shell 排序比 Hibbard 更快。

按照大O表示法，Hibbard是O(N^1.5)，Shell是O(N^2)，这让我觉得随着数据集规模的增大，Hibbard应该比Shell有更大的改进。谁能告诉我为什么我的结果可能不如预期？

我知道 O 表示法是最坏情况下的复杂度，但似乎性能应该与该表示法更好地对齐。

这是我用 JAVA 编写的代码: (注意:unsortedArray 是在前面声明和初始化的)

{
    int temp;
    int[] sortedArray = unsortedArray.clone();
    printArray();
    int k = (int)(Math.log(sortedArray.length)/Math.log(2));
    int gap = (int)(Math.pow(2,k)-1);
    int count = 0;
    long endTime;
    long startTime = System.nanoTime();

    while (gap > 0)
    {
        for (int g = 0; g < gap; g++)
        {
            for (int d = g + gap; d < sortedArray.length; d = d + gap)
            {
                for (int i = d; i - gap >= 0; i = i - gap)
                {                          
                    if (sortedArray[i - gap] <= (sortedArray[i]) )
                    {
                        break;
                    }
                    count++;
                    temp = sortedArray[i];
                    sortedArray[i] = sortedArray [i-gap];
                    sortedArray[i-gap] = temp;

                }
            }
        }

        k = k -1;
        gap = (int)(Math.pow(2,k)-1);
    }
    endTime = System.nanoTime();
    System.out.println("The total time for hibbard sort is" + (endTime-startTime));
    System.out.println("the number of swaps for hibbard sort is" + count);
}

Answer 1

测量这两种间隙生成算法之间的时间复杂度差异实际上比这更棘手。

考虑为两者提供经过排序的数据序列并假设 n=8。对于 Shell，我们得到空位序列 {4,2,1}，对于 Hibbard，我们得到空位序列 {7,3,1}。要运行排序序列需要 (Shell) (n-4)+(n-2)+(n-1) 或 17 次比较和 (Hibbard) (n-7)+(n-3)+(n- 1) 或 13。

很明显，给定 n 个元素的随机序列，您不能得出 Hibbard 将在 Shell 时间的 13/17 内执行的结论。

可能会发现，给定的、随机生成的序列被证明更适合使用 Shell 而不是 Hibbard 进行排序，反之亦然。确定哪个更好的唯一方法是测试所有可能的数据序列组合并计算它们所需的平均比较次数。当 n=8(只有 n!或 40320 个组合)时，这很容易完成，但是当 n=100 或 1000 时……“更多”困难。

当 n=8 时，使用上述两个间隙对所有可能的序列进行 Shellsort(包括插入排序和最佳 shellsort 间隙以供比较):

                       number of comparisons when n=8
gap sequence           minimum   average   maximum   reverse
{1} (insertion sort)      7       19.28      28        28
{5,1} (best gap)         10       17.4       24        15 
{4,2,1} (Shell)          17       21.82      30        22
{7,3,1} (Hibbard)        13       18.57      24        20

所以在n=8的情况下，Hibbard比Shell好很多，比插入排序好但是比best gap sequence差。有趣的是，对于最佳间隙，对数据的反向序列进行排序比平均情况更快!

如果我们查看 n=14，我们会发现 Shell 和 Hibbard 得到相同的序列，{7,3,1} - 显然这两种算法都不会比另一种更好 - 在 n=16 时我们得到 {8 ,4,2,1} 和 {15,7,3,1}，分别。这导致 Hibbard (n*4)-(15+7+3+1) 或 38 比较的最佳情况比 Shell (n*4)-(8+4+2+1) 或 49 更好。

随着 n 的增加，哪个会比另一个更好？在我看来，最好的间隙序列取决于 n，它应该给 Shell 作为 Hibbard 的边缘，例如，当 8 <= n < 16 和 {15,7, 3,1} 当 16 <= n <32 时:基本上是“一刀切”。

Shellsort 想要移动初始间隙相距很远的值，而当 n=16、17 或 18 且间隙为 15 时，对于 Hibbard 这可能是正确的，但当 n 接近上限时，情况就不太正确了限制为 31。

但是，这并不是说 Shell 会产生更好的间隙序列。当 n 接近其序列的上限时，n/2 的第一个间隙将始终受到与 Hibbard 的初始间隙相同的问题的阻碍。

所以我的猜测是 Shell 会给出比 Hibbard 和插入排序都差的稳定结果。 Hibbard 的结果从初始差距的下限到上限 n 将不成比例地增加。在某处，当 n 接近 n 的上限时，Hibbard 的性能也将开始比插入排序差。

除了计算间隙本身的值外，还必须确定间隙的数量。如前所示，当 n=8 时两个间隙就足够了，但当 n=10 或更多时也是如此吗？例如，从 2 <= n < 6 开始，插入排序将比任何 shellsort 都快，但是从 n=6 开始，两个间隔允许 Shellsort 击败插入排序。