我正在寻找壳牌排序的最坏情况。
根据this，最坏的情况是O(N^3/2)
但是here，据称最坏的情况是O((N log N)^2))。
我认为最坏的情况应该是在奇数位置包含最大价位的序列。但是，here一些间隙序列以Θ(N^3/2)的复杂性引入。
我试图弄清楚Shell排序的实际最坏情况是什么。到目前为止，根据上述论文，最坏的情况是O((N log N)^2))而不是Θ(N^3/2)。另外，here建议最坏的情况分析，显然不是Θ(N^3/2)。
Here，在某些算法中以O(N^2)作为最坏情况进行了时间复杂度分析。
但是，我完全迷路了。 Shell排序最坏的情况是什么？
最佳答案
看起来不仅有一个“ 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）。这就是我在想的最大可能的复杂度，是间隙严格减少的间隙序列（没有严格降低的间隙序列并不有趣，因为它们可能是任意坏的）。