时间复杂度为Shell排序？复杂度、时间、Shell

2023-09-11 04:40:33 作者：夏筝

首先，这里是我的Shell排序code（使用Java）：

First, here's my Shell sort code (using 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;
}

这是一个正确的实施壳牌排序（忘记，现在关于最有效的差距序列 - 例如，1,3,7,21 ......）？我问，因为我听说壳牌的最好情况下的时间复杂度排序为O（n）。（见 http://en.wikipedia.org/wiki/Sorting_algorithm ）。我看不到这样的效率水平正由我的code ++实现的。如果我说启发式，那么是的，但因为它的立场，没有。

Is this a correct implementation of Shell sort (forgetting for now about the most efficient gap sequence - e.g., 1,3,7,21...)? I ask because I've heard that the best-case time complexity for Shell Sort is O(n). (See http://en.wikipedia.org/wiki/Sorting_algorithm). I can't see this level of efficiency being realized by my code. If I added heuristics to it, then yeah, but as it stands, no.

话虽这么说，我现在主要的问题 - 我有困难，计算大O的时间复杂度为我Shell排序的实现。我确定了最外面的环为O（log n）的，中间环为O（n）和最内层的环也为O（N），但我知道内部的两个循环就不会真正为O（ N） - 他们会比这少得多 - 他们应该怎样呢？因为很明显这个算法运行效率远远高于O（（log n）的N ^ 2）。

That being said, my main question now - I'm having difficulty calculating the Big O time complexity for my Shell sort implementation. I identified that the outer-most loop as O(log n), the middle loop as O(n), and the inner-most loop also as O(n), but I realize the inner two loops would not actually be O(n) - they would be much less than this - what should they be? Because obviously this algorithm runs much more efficiently than O((log n) n^2).

任何指导是多少AP preciated因为我很失落！：P

Any guidance is much appreciated as I'm very lost! :P

时间复杂度为Shell排序？复杂度、时间、Shell

推荐答案