-1

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

我使用Python生成的随机数组来测量shell排序的时间复杂度，但发现它的时间复杂度更符合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

shell排序时间复杂度分析

4

3 回答 3

0

我研究了较小 n 的 shellsort，并且我可以明确指出，对于 n = 10，产生最佳平均值（比较次数）的间隙序列，我的软件在 n 上进行了测试！不同的排序（整个集合）和 2^(n-2) 个间隙序列（n = 10 的所有可能序列）是 {9,6,1}。

在最坏的情况下，平均值显然是 O(n * log(n))。

最好的情况类似于插入排序的 n-1 比较 - O(n) 复杂度 - 最好的情况（已经排序的数据），不仅因为它可以类似地计算：

(n-9)+(n-6)+(n-1) = (n * # of gaps)-sum(gaps) = 14。

我知道大多数人会说这是 O(n * log(n)) 复杂度。就个人而言，我认为这是没有根据的，因为它不需要估计：对于任何间隙序列处理的任何 n，最好的情况很容易且准确地确定。

我会固执地把这个回家：为了争论，我们假设任何 shellsort 的最佳情况是 (n * # of gaps)。对于 n = 10 & # of gaps = 3，最好的情况是 10 * 3 或 30。这会是 O(n) 复杂度吗？我明白为什么会这样。然而，shellsort 的最佳情况明显小于 (n * # of gaps) 那么为什么它是 O(n * log(n))？

OP 有可能（尽管极不可能）设法为他的 n 确定最佳（或接近它）间隙序列，从而导致 O(n * log(n)) 复杂度。但确定这一点需要比胆量提供更多的分析。

于 2021-09-29T19:44:14.610 回答
0

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) 的声明可能是错误的，这取决于算法的确切实现。

于 2018-09-27T07:47:03.877 回答
0

Shell 排序复杂度存在很多问题，并且怀疑通过一些适当的参数选择和某些输入，其复杂度可能为 O(n.logn)。

于 2018-09-27T08:06:22.097 回答