我已经为我的数据结构类研究了很多关于时间复杂性的问题。我的任务是报告Shell排序算法并解释其时间复杂性(最佳/最差/平均情况(。我发现了这个网站https://stackabuse.com/shell-sort-in-java/这表明这种Shell排序算法的时间复杂性：
void shellSort(int array[], int n){
//n = array.length
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;
}
}
}
是O(n log n(。但问题是，我仍然对使logn成为logn或nlogn的含义感到困惑。
我也尝试了步数法，但同样，我不知道从哪里开始，所以我只是从上面的网站复制并做了这个。
void shellSort(int array[], int n){
//n = array.length
for (int gap = n/2; gap > 0; gap /= 2){ //step 1 = runs logn times
for (int i = gap; i < n; i += 1) { //step 2 = runs n-gap times
int temp = array[i]; //step 3 = 1
int j; //step 4 = 1
for (j = i; j >= gap && array[j - gap] > temp; j -= gap){ //step 5 = i/gap times
array[j] = array[j - gap]; //step 6 = 1
}
array[j] = temp; //step 7 = 1
}
}
}
但我不知道这是否正确，我只是基于这个网站。https://stackabuse.com/shell-sort-in-java/.
我也试过比较插入排序和外壳排序之间的移动总数，因为外壳排序是插入和气泡排序的概括。我将在下面附上图片。我还使用了一个在线数字生成器，它会给我100个随机数，复制它并将其应用于插入排序和外壳排序，并将其分配为要排序的数组。
结果就是这样，
插入排序的移动总数=4731
外壳排序的移动总数=195
Shell Sort实现，告诉我它执行的移动总数
插入排序实现，告诉我它做的移动总数
我从所有这些中了解到，尽管Shell排序是插入排序的推广，但当涉及到排序大型数组(如100个元素(时，Shell排序比插入排序快2倍。
但最终的问题是，有没有一种初学者的方法可以像这种Shell排序算法一样计算时间复杂性？
您必须查看函数的大O或大Theta分析。你的外循环在每次迭代中都被减半，所以它运行的总时间是log n。现在，当你观察你的内循环时，它最初从n/2到n一直运行到1到n或2到n，这取决于n的初始大小，所以它的执行时间将是n/2+n/4+。。。。n/2^k，它是一个"调和级数"(如果你因子n->n(1/2+1/4+…+1/2^k(等于nlogn，你也可以搜索几何级数。现在，每个列表可以在某种程度上排序的最佳情况将是Ω(nlogn(，因为在外循环的中间，我们将找到最优解，所以我们可以说nlogn是它的下界-意味着它肯定等于或大于它-因此，我们可以说平均情况是θ(nlog^2 n(，意味着它在它的下界中-请注意平均情况I使用大θ。现在，如果我们假设列表是完全相反的，那么外循环将一直运行到最后，即logn。内循环将运行nlogn，所以总时间将是nlog^2(n(，我们可以说它将是O(nlog^2(n(((我们也可以使用大O，但theta更好，你可以向上搜索theta如何提供紧边界，而大O只提供上界(。因此，我们也可以说最坏的情况是O(n^2(，这在某些情况下是相对正确的。
我建议你看看Big-O和Big Theta以及Big Omega，它们在这种情况下也很有用。
然而，shell算法最精确的数学表示将是O(n^3/2(。然而，仍然存在争论和分析。
我希望这能有所帮助。
首先，我将展示算法永远不会比O(n^2)慢，然后我将展示最坏情况下的运行时间至少是O(n^2)。
假设n是2的幂。我们知道插入排序的最坏情况是O(n^2)。当h对数组进行排序时，我们将执行h插入排序，每个插入排序都针对大小为n / h的数组。所以h排序通过的复杂度是O(h * (n / h)^2) = O(n^2 / h)。整个算法的复杂性现在是n^2 / h的和，其中h是高达n / 2的二次方。这是一个具有第一项n^2、公比1 / 2和log2(n)项的几何级数。利用几何级数求和公式给出了CCD_ 16。
考虑通过交织两个递增序列创建的数组，其中一个序列中的所有元素都大于另一个序列的所有元素，例如[1, 5, 2, 6, 3, 7, 4, 8]。由于这个数组是两次排序的，所以除了最后一次之外的所有过程都不执行任何操作。在最后一次遍历中，索引i中i所在的元素甚至必须移动到索引i / 2，该索引使用O(i / 2)操作。所以我们有1 + 2 + 3 + ... + n / 2 = (n / 2) * (n / 2 + 1) / 2 = O(n^2)。