algorithm - 预排序列表上的 Shell 排序运行时间(最佳情况)

Question

如果列表是预先排序的(最好的情况)，我对 shell 排序的运行时间感到困惑。是 O(n) 还是 O(n log n)？

    for(k=n/2; k>0; k/=2)
       for(i=k; i<n; i++)
           for(j=i;j>k; j-=k)
              if(a[j-k]>a[j]) swap
              else break;

shell排序是基于插入排序的，插入排序对于预排序的list有O(n)的运行时间，但是通过引入gaps(最外层循环)，不知道会不会让shell的运行时间对预排序列表进行排序 O(n log n)。

谢谢你的帮助

Answer 1

在数据已经排序的最佳情况下，最内层的循环永远不会交换。它总是会立即中断，因为已知左侧值小于右侧值:

for(k=n/2; k>0; k/=2)
   for(i=k; i<n; i++)
       for(j=i;j>k; j-=k)
          if(false) swap
          else break;

因此，该算法可以简化为:

for(k=n/2; k>0; k/=2)
   for(i=k; i<n; i++)
      no_op()

然后最好的情况变成:

O((n - n/2) + (n - n/4) + (n - n/8) + ... + (n - 1)) 
= O(nlog(n) - n) 
= O(nlog(n))

也就是说，according to Wikipedia ，Shell 排序的其他一些变体确实具有 O(N) 最佳情况。