algorithm - Shell排序的时间复杂度？

Question

首先，这是我的 Shell 排序代码(使用 Java):

public char[] shellSort(char[] chars) {
    int n = chars.length;
    int increment = n / 2;
    while(increment > 0) {
        int last = increment;
        while(last < n) {
            int current = last - increment;
            while(current >= 0) {
                if(chars[current] > chars[current + increment]) {
                    //swap
                    char tmp = chars[current];
                    chars[current] = chars[current + increment];
                    chars[current + increment] = tmp;
                    current -= increment;
                }
                else { break; }
            }
            last++;
        }
        increment /= 2;
    }
    return chars;
}

这是 Shell 排序的正确实现吗(暂时忘记最有效的间隙序列 - 例如 1,3,7,21...)？我问是因为我听说 Shell 排序的最佳时间复杂度是 O(n)。 (参见 http://en.wikipedia.org/wiki/Sorting_algorithm)。我看不到我的代码实现了这种效率水平。如果我向其中添加启发式方法，那么是的，但就目前而言，不是。

话虽这么说，但我现在的主要问题是 - 我在计算我的 Shell 排序实现的 Big O 时间复杂度时遇到了困难。我确定最外层的循环为 O(log n)，中间的循环为 O(n)，最内层的循环也为 O(n)，但我意识到内部的两个循环实际上不会是 O( n) - 他们会比这少得多 - 他们应该是什么？因为显然这个算法的运行效率比 O((log n) n^2) 高得多。

非常感谢任何指导，因为我很迷茫! :P

Answer 1

您实现的最坏情况是 Θ(n^2)，最好情况是 O(nlogn)，这对于 shell-sort 是合理的。

最佳情况∊O(nlogn):

最好的情况是数组已经排序。这意味着内部 if 语句永远不会为真，从而使内部 while 循环成为恒定时间操作。使用您用于其他循环的边界可以得到 O(nlogn)。 O(n) 的最佳情况是通过使用恒定数量的增量来实现的。

最坏情况∊O(n^2):

给定每个循环的上限，最坏情况的复杂度为 O((log n)n^2)。但是为间隙大小 g 添加另一个变量。内部 while 中需要的比较/交换次数现在 <= n/g。中间while的比较/交换次数<= n^2/g。将每个间隙的比较/交换次数上限相加:n^2 + n^2/2 + n^2/4 + ... <= 2n^2 ∊ O(n^2)。这与您使用的间隙的已知最坏情况复杂性相匹配。

最坏情况∊Ω(n^2):

考虑一个数组，其中所有偶数位置的元素都大于中位数。直到我们到达最后一个增量 1 时，才会比较奇数和偶数元素。最后一次迭代所需的比较/交换次数为 Ω(n^2)。