为什么 shell 排序的时间复杂度在我的数据中是 nlogn？

Question

环境：python3.6、Anaconda 5.1、Jupyter notebook、numba。

我用Python生成的随机数组来衡量shell sort的时间复杂度，但是发现它的时间复杂度更符合NlogN。我知道shell排序的时间复杂度是O(n^2)，我很困惑。

外壳排序代码：

def shell_sort(list):

    n = len(list)

    gap = n // 2

    while gap > 0:

        for i in range(gap, n):

            temp = list[i]

            j = i

            while j >= gap and list[j - gap] > temp:

                list[j] = list[j - gap]

                j -= gap

            list[j] = temp

        gap = gap // 2

    return list

Answer 1

O(n^2) 只是最坏情况下的时间复杂度，因此该算法可以在比随机输入甚至平均（甚至几乎所有输入......）上运行更短的时间。此外，Shellsort 的复杂性取决于您选择的“间隙序列”。某些间隙序列导致最坏的时间情况小于 O(n^2)，例如间隙序列的 O(n^1.5)1, 4, 13, 40, 121, ...或什至 O(nlog^2(n)) 1, 2, 3, 4, 6, 8, 9, 12, ...（均归功于 Pratt，1971）。换句话说：仅仅尝试一个输入根本不重要，并且根据算法的确切实现，关于 O(n^2) 的说法可能是错误的。

Answer 2

相对于shell排序复杂性存在很多问题，并且怀疑具有一些适当的参数选择和一些输入，其复杂性可以是O（n.logn）。