sorting - 希尔排序的最坏情况 : Θ(N^3/2) or O((NlogN)^2)?

Question

我正在寻找希尔排序的最坏情况。 根据this ，最坏的情况是O(N^3/2) 但是here ，据称最坏情况是O((N log N)^2))。

我认为最坏的情况应该是在奇数位置包含最大值的序列。然而，here一些间隙序列的引入具有θ(N^3/2)复杂度。

我试图找出希尔排序的实际最坏情况是什么。到目前为止，根据上述论文，最坏的情况是 O((N log N)^2)) 而不是 θ(N^3/2)。另外，here建议最坏的情况分析，显然不是 θ(N^3/2)。

Here ，对某种算法进行时间复杂度分析，以O(N^2)作为其最坏情况。

但是，我完全迷失了。希尔排序最坏的情况是什么？

Answer 1

看起来不只是一个“Shellsort”，而是一系列由所谓的间隙序列参数化的排序函数。 Shellsort 的工作原理是对列表进行多次 h 排序，以减小 h 的值。 h 的使用顺序决定了 Shellsort 的执行方式。有些序列给出 O(N^3/2)，有些序列给出 O(N^2)，其他序列给出 O(N log^2 N)，等等。

您看到的每个引用文献都可能使用不同的间隙序列来推导其渐近边界。

编辑:考虑最坏的可能间隙序列(无重复)n、n-1、n-2、...、 1。获取运行时:

h    sublists sublist size    comparisons
n    n        1 (n)           0
n-1  n-1      1 (n-2), 2 (1)  1
n-2  n-2      1 (n-4), 2 (2)  2
...
n/2  n/2      2 (n/2)         2n
...
n/3  n/3      3 (n/3)         3n
...
n/4  n/4      4 (n/4)         4n
...
n/n           n (1)           n^2

所以答案将类似于 n(1+2+...+n) = n^2(n+1)/2，或 O(n^3)。这就是我认为最大可能的复杂性是间隙严格递减的间隙序列(不严格递减的间隙序列并不有趣，因为它们可能是任意糟糕的)。