java - 有没有一种简单的方法可以找到时间复杂度？

Question

我们的老师在让我们报告希尔排序之前，并没有教我们如何分析算法的运行时间。

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

//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;
      }
    }
  }

Answer 1

欢迎来到堆栈溢出!通常，排序算法的时间复杂度是通过执行的键比较的数量来衡量的。我们可以首先考虑需要最少数量的键比较才能完全排序的输入(最好情况)，然后再考虑需要最多数量的输入(最坏情况)。通常，最好的情况是排序列表，最坏的情况可能是按相反顺序排序的列表，尽管某些分而治之算法可能不是这种情况。

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

对于数组上的每个循环，这都会增加时间复杂度因子“n”，而嵌套循环会“倍增”此复杂度。即 2 个嵌套循环的复杂度为 n^2，3 个嵌套循环的复杂度为 n^3。

重复将数组分成两半通常会产生“log(n)”的时间复杂度因子。