Shell 排序最坏情况时间复杂度

Question

我想通过 shell 排序的代码了解最坏情况分析。你们能帮我找出答案吗？ while循环会执行O(log n)次，for循环O(n)次；那么复杂性是如何变成 O(n^2) 的呢？一个完整的答案将不胜感激；我已经坚持了一天。

int i, n = a.length, diff = n/2, interchange, temp;
while (diff > 0) 
{ 
  interchange=0;
  for (i = 0; i < n - diff; i++) 
  {
    if (a[i] > a[i + diff]) 
    { 
      temp = a[i];
      a[i] = a[i + diff];
      a[i + diff] = temp;
      interchange = 1;
    }
  }

  if (interchange == 0) 
  {
    diff = diff/2;
  }
}

Answer 1

您的算法不是 shell 排序。 Shell 排序通过多次执行基本的冒泡排序来工作。每次，您只考虑它们之间有 k 个元素间隙的元素。 k 由以 1 结尾的递减序列给出。您的序列是 n/2、n/4、n/8、...、1，这很好。但是您并没有对该序列的每个成员执行冒泡排序；你只执行一次传球，这是不够的。 O(n^2) 的最坏情况复杂度是由于冒泡排序。

请注意，在您的情况下，由于序列的长度不是恒定的，如果您修复算法，最坏情况下的复杂度将是 O(n^2 * logn)。

关于算法的更多细节，wikipedia是你的朋友。

稍后编辑：

更正后的代码是：

int i,n=a.length,diff=n/2,interchange,temp;
 while(diff>0) { 
 interchange=0;
 for(i=diff; i<n;i++) {
    temp=a[i];
    for (j = i; j >= gap && a[j-gap] > temp; j -= gap)
      a[j] = a[j-gap];  
    a[j]=temp;
  }
  diff=diff/2;
 }

请注意，我没有检查它，所以我可能是错的。现在，你能看到复杂度为 O(n^2) 的嵌套 for 循环吗？

Answer 2

您看到的问题是混淆了平均情况和最坏情况。在一般情况下，diff 会定期更新并划分，导致 while 循环执行接近 lgn 次。但是，由于交换数据，您有可能在每个循环中交换变为 1。如果数据以最坏的可能方式排序，则每个循环都会移动数据。这将导致 while 循环执行 n 次而不是 lgn。对于 o(n) 处的 while 循环和 for 循环，您正在查看 o(n^2)

考虑对长度为 4 的数组进行排序，数字为：4、3、2、1。

第一个循环，找到并切换 4 和 2，以及 3 和 1。这使得你的循环：2、1、4、3。

下一个循环，没有任何反应，交换为 0，所以它减半了你的差异。

第三个循环，找到并切换 2 和 1，以及 4 和 3：1, 2, 3, 4

interchange是1，diff还是1，所以你再做一个循环。没有任何反应，diff 变为 0.5 退出循环。

在这种情况下，while 循环执行 n 次，for 循环执行 n 次。

Shell 排序最坏情况时间复杂度

Shell sort worst case time complexity

java

algorithm

shell

performance

time-complexity