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 Sort的最佳时间复杂度是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.中间的比较/交换次数是<= n ^ 2/g.将每个间隙的比较/交换次数的上限加在一起:n ^ 2 + n ^ 2/2 + n ^ 2/4 + ... <= 2n ^2∈O(n ^ 2).这与您使用的间隙的已知最坏情况复杂性相匹配.

最坏的情况εΩ(n ^ 2):

考虑所有偶数定位元素大于中位数的数组.在我们达到1的最后一个增量之前,不比较奇数和偶数元素.最后一次迭代所需的比较/交换的数量是Ω(n ^ 2).