Есть ли простой способ найти сложность времени?

Question

Наша учительница не учила нас, как анализировать время выполнения алгоритма, прежде чем она захотела, чтобы мы сообщали о сортировке 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), то вы знаете, что среднее значение одинаково. В противном случае вы можете получить его математически с помощью вероятностного анализа c.

Для каждого l oop в массиве это добавит фактор сложности времени n, а вложенные циклы "умножат" это сложность. то есть 2 вложенных цикла дают сложность n ^ 2, а 3 вложенных цикла дают сложность n ^ 3.

Разделение массива пополам многократно часто дает вам фактор сложности времени log (n) .