java - 分析希尔排序算法(大O)

Question

这就是希尔排序算法。

  void shellSort(int array[], int n){
    for (int gap = n/2; gap > 0; gap /= 2){
        for (int i = gap; i < n; i += 1) {
           int temp = array[i];
           int j;

           for (j = i; j >= gap && array[j - gap] > temp; j -= gap){
              array[j] = array[j - gap];
           }
           array[j] = temp;
        }
      }
  }

我确定该算法的外循环运行logn次，但我不确定中间循环和最内循环。本站https://stackabuse.com/shell-sort-in-java/说中间循环运行n-gap次，而最里面的循环运行i/gap但我不太确定。请帮助我理解这个算法中中间和最内层的循环是如何运行的，非常感谢任何帮助我的人。

Answer 1

这些是算法中的循环:

for (int gap = n/2; gap > 0; gap /= 2) {
  for (int i = gap; i < n; i += 1) {
    for (j = i; j >= gap && array[j - gap] > temp; j -= gap) {
    }
  }
}

让我们从i 上的循环开始。它从 gap 开始，并以 1 为增量转到 n。 j 上的下一个循环从当前 i 开始并下降gap，直到小于gap。因此，j 上的循环对于 gap 和 2*gap 之间的 i 执行一次，对于 执行两次i 位于 2*gap 和 3*gap 之间，i 位于 3*gap 之间三次和4*gap等等。

这意味着 j 循环将对 gap 不同的 i 值执行一次，对 gap 执行两次不同的i值，三次gap不同的i值，等等

i 的最大值为 n，因此 j 上的循环最多可以执行 j_max = (n - 间隙)/gap 次。 j 循环的执行总数为

1+1+...+1+1 + 2+2+...+2+2 + 3+3+...+3+3 + .... + j_max+j_max+...+j_max+j_max
|_________|   |_________|   |_________|          |_________________________|
 gap times     gap times     gap times                    gap times 

这个总和等于

gap*(sum from 1 to j_max) = gap * j_max(j_max + 1) / 2 = O(gap * ((n-gap)/gap)^2) = O((n-gap)^2/gap)

这将在外循环中针对不同的gap值重复进行，因此复杂度为O-big

sum((n-gap)^2/gap, for gap = n/2, n/4, n/8, ...., 4, 2, 1)

扩展:

(n^2 - 2*n*gap + gap^2)/gap = n^2*(1/gap) - 2*n + gap

第一项等于 n 的平方乘以以下值:

1/(n/2),  1/(n/4),  1/(n/8), ..... 1/4,  1/2, 1/1

或

2/n, 4/n, 8/n, ....., n/n

这是 2 的幂除以 n 的总和，因此第一项给出总计

n^2/n * 2^(log2 n) = n^2

第二项是 -2*n 和 log2 n 次，因此复杂度为

n*log2 n

最后一项是间隙之和，因此它是2的幂之和，其复杂度为n。 将所有这些结合在一起，我们得到最坏情况的复杂度为 O(n^2)。