有没有一种简单的方法来计算时间复杂度？

Question

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

我只想知道是否有一种简单的方法可以找到像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;
      }
    }
  }

Answer 1

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

至于平均情况，一旦你得到了最好和最坏的情况，你就知道平均值介于两者之间。如果两者都有相同的时间复杂度类(通常是'Big Oh‘类)，那么您就知道平均值是相同的。否则，您可以通过概率分析从数学上推导出它。

对于数组上的每个循环，这将添加一个'n‘的时间复杂性因子，而嵌套循环将’成倍‘地增加这种复杂性。也就是说，2个嵌套循环的复杂度为n^2，3个嵌套循环的复杂度为n^3。

重复地将数组分成两半通常会给出'log(n)‘的时间复杂度因子。