02.05.065 Оценка эффективности - justjune/AiSD2026 GitHub Wiki

Раздел 2.5 книги Скиена посвящён практическому применению асимптотического анализа.

Раздел целиком построен на разборе конкретных примеров.

Оценка эффективности алгоритма сортировки методом выбора на языке C (Книга Скиена стр 65, листинг 2.1)

Алгоритм последовательно находит минимальный элемент в неотсортированной части и ставит его на текущую позицию.

void selection_sort(item_type s[], int n) {
  int i, j;
  int min;
  for (i = 0; i < n; i++) {
    min=i;
    for (j = i + 1; j < n; j++) {
      if (s[j] < s[min]) {
        min=j;
      }
    }
    swap(&s[i], &s[min]);
  }
}

Внешний цикл исполняется (n) раз. Внутренний — (n-(i+1)) раз. Значит, в худшем случае время работы не более $n \times n = O(n^2)$.

Точный подсчёт числа выполнений оператора if:

$T(n) = \sum_{i=0}^{n-1} \sum_{j=i+1}^{n-1} 1 = \sum_{i=0}^{n-1}(n-i-1) = \frac{(n-1)(n-2)}{2}$

Это формула сложения неотрицательных целых чисел в убывающем порядке, начиная с $n-1$: $T(n)=(n−1)+(n−2)+(n−3)+…+2+1$

Верхняя граница: имеется не более (n) элементов, значение каждого из которых не превышает (n - 1). Таким образом: $T(n) \leq n(n-1) = O(n^2)$

Нижняя граница: имеется (n/2) элементов, каждый из которых больше чем (n/2), за которыми следуют (n/2) элементов, каждый из которых больше нуля. Соответственно: $T(n) \geq (n/2)\cdot(n/2) + (n/2)\cdot 0 = \Omega(n^2)$

Вместе с результатами обозначения O-большое это говорит нам, что время исполнения равно $\Theta(n^2)$, т. е. сложность сортировки методом выбора является квадратичной.

Сортировка методом выбора выделяется среди алгоритмов сортировки тем, что занимает абсолютно одинаковое время для всех (n!) возможных экземпляров ввода, поскольку $T(n) = n(n-1)/2$ для всех $n \geq 0$, $(T(n) = \Theta(n^2))$.

Оценка эффективности алгоритма сортировки ставками на языке С (Книга Скиена стр 67, листинг 2.2)

На каждом шаге алгоритм берёт первый элемент неотсортированной части и вставляет его на своё место в отсортированную, сдвигая бо́льшие элементы вправо.

for (i = 1; i < n; i++) {
    j = i;
    while ((j > 0) && (s[j] < s[j - 1])) {
        swap(&s[j], &s[j - 1]);
        j = j-1;
    }
}

Сколько итераций осуществляет внутренний цикл while? На этот вопрос сложно дать однозначный ответ, поскольку цикл может быть остановлен досрочно, если произойдет выход за границы массива (j > 0) или элемент окажется на должном месте в отсортированной части массива (s[j] < s[j-1]). Так как в анализе наихудшего случая нам надо найти верхнюю границу времени исполнения, то мы игнорируем досрочное завершение и полагаем, что количество исполняемых в этом цикле итераций всегда будет i. Более того, мы можем упростить еще больше и допустить, что всегда исполняется n итераций, т.к. i<n. А раз внешний цикл исполняется n раз, то для алгоритма сортировки вставками должен быть квадратичным, т.е. $O(n^2)$.

Верхняя граница. Такой грубый анализ методом округления всегда оказывается результативным в том смысле, что полученная верхняя граница времени исполнения (О-большое) всегда будет правильной: $T(n)\leq n \times n=O(n^2)$

Нижняя граница. Наихудший случай сортировки вставками происходит тогда, когда каждый вставляемый элемент нужно переместить в самое начало отсортированной области. Такая ситуация возникает, когда ввод отсортирован в порядке, обратном требуемому. Каждый из последних n/2 элементов ввода должен переместиться как минимум через n/2 элемента, чтобы занять правильное место, занимая, по крайней мере, время: $T(n) \geq (n/2)^2=\Omega(n^2)$

Вместе с результатами обозначения O-большое это говорит нам, что время исполнения равно $\Theta(n^2)$, т.е. сложность сортировки методом вставками является квадратичной.