shell 排序的最坏情况：Θ(N^3/2) 或 O((NlogN)^2)？
Worst scenario for shell sort: Θ(N^3/2) or O((NlogN)^2)?
我正在寻找 Shell 排序的最坏情况。
根据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)。这就是我认为最大可能的复杂性是 gap 严格减少 gap 序列（不严格减少的 gap 序列并不有趣，因为它们可能是任意糟糕的）。
我正在寻找 Shell 排序的最坏情况。
根据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)。这就是我认为最大可能的复杂性是 gap 严格减少 gap 序列（不严格减少的 gap 序列并不有趣，因为它们可能是任意糟糕的）。