0

我们的老师没有教我们如何分析算法的运行时间，然后她想让我们报告一下Shell sort。

我只想知道是否有一种简单的方法可以找到像 shell 排序这样的算法的平均/最佳/最差情况性能。

//for references

class ShellSort{
  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;
      }
    }
  }
4

1 回答 1

1

欢迎堆栈溢出！通常，排序算法的时间复杂度是通过执行的键比较次数来衡量的。可以首先考虑需要最少数量的键比较才能完全排序的输入（最佳情况），然后跟进需要最多数量的输入（最坏情况）。通常，最好的情况是排序列表，最坏的情况可能是按相反顺序排序的列表，尽管对于某些分而治之的算法可能并非如此。

至于平均情况，一旦你得出最好和最坏的情况，你就会知道平均值介于两者之间。如果两者具有相同的时间复杂度类（通常是“Big Oh”类），那么您知道平均值是相同的。否则，您可以通过概率分析以数学方式推导出它。

对于数组上的每个循环，这将增加一个时间复杂度因子“n”，而嵌套循环将“倍增”这种复杂性。即 2 个嵌套循环给出 n^2 的复杂度，3 个嵌套循环给出 n^3 的复杂度。

重复将数组分成两半通常会给您一个时间复杂度因子“log(n)”。

于 2020-02-29T03:42:52.820 回答