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

Question

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

我只是想知道是否有一种简单的方法可以找到像 shell 排序这样的算法的 average/best/worst 案例性能。

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

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

至于平均情况，一旦推导出最佳和最差情况，您就会知道平均值介于两者之间。如果两者具有相同的时间复杂度 class（通常是 'Big Oh' class），那么您就知道平均值是相同的。否则，您可以通过概率分析从数学上推导出它。

数组上的每个循环都会增加 'n' 的时间复杂度，而嵌套循环会增加 'multiply' 这个复杂度。即 2 个嵌套循环给出 n^2 的复杂度，3 个嵌套循环给出 n^3 的复杂度。

将数组重复分成两半通常会给您带来 'log(n)' 的时间复杂度。

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

Is there a simple way to find the time complexity?

java

performance

time-complexity

shellsort