壳Vs.Hibbard时间复杂度比较
我正在做一个实验来比较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);
}回答 2
Stack Overflow用户
发布于 2016-06-14 20:03:38
衡量这两种差距生成算法之间的时间复杂度差异实际上要比这更棘手一些。
考虑为两者提供一个排序的数据序列，并假设为n=8。对于壳牌，我们得到的间隙序列是{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时，"more“比较困难。
当n=8使用上面的两个间隙时，对所有可能的序列进行外壳排序(包括插入排序和最佳外壳排序间隙以进行比较)：
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好得多，比插入排序好，但比最佳间隙序列差。有趣的是，对于最佳间隔，对颠倒的数据序列进行排序比一般情况更快！
如果我们查看n=14，我们发现壳牌和Hibbard的结果是相同的序列{7,3,1} -其中显然两个算法都不会比另一个更好-在n=16我们分别得到{8,4,2,1}和{15,7,3,1}。这为Hibbard (n*4)-(15+7+3+1)或38次比较带来了比壳牌(n*4)-(8+4+2+1)或49更好的最佳情况。
随着n的增加，哪一个会比另一个更好？在我看来，最好的间隙序列取决于n，这应该给壳牌一个边缘，例如，当8 <= n< 16时具有相同的序列{7,3,1}，当16 <= n<32时具有相同的序列{15,7,3,1}：基本上“一刀切”。
外壳排序希望移动初始间隙中相距较远的值，当n=16为17或18，间隙为15时，这对于Hibbard可能是正确的，但当n接近上限31时，这种情况就不那么正确了。
然而，这并不是说Shell会产生更好的gap序列。当n接近序列的上限时，n/2的第一个间隙总是会受到与Hibbard的初始间隙相同的问题的阻碍。
所以我的猜测是Shell会给出比Hibbard更差的稳定结果，而且可能还会插入排序。Hibbard的结果从初始差距的下限到上限n将不成比例地增加。在某些地方，当n接近上限n时，Hibbard的性能也将开始比插入排序差。
除了计算间隙本身的值之外，还必须确定间隙的数量。如前所述，两个间隙在n=8时就足够了，但当n=10或更多时也是如此吗？例如，从2 <= n<6开始，插入排序将比任何外壳排序都快，但是从n=6开始，两个间隙允许外壳排序优于插入排序。
Stack Overflow用户
发布于 2015-11-07 20:59:29
我认为性能可能会受到JVM的影响，所以最好用另一种语言来衡量它，比如C或C++。
关于Java，C++和C#中的外壳排序算法的更多信息可以在这里找到：
http://www.programming-algorithms.net/article/41653/Shell-sort
关于测量算法复杂度的信息在这里：
http://www.programming-algorithms.net/article/44682/Asymptotic-complexity
希望这能有所帮助。
https://stackoverflow.com/questions/30740413
复制相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号