Здравствуйте!
Не мог бы кто-нибудь объяснить каким образом в книге "Алгоритмы и структуры данных" подсчитывается количество сравнений для алгоритмов сортировки. Никак в толк не возьму.
Скажем, сортировка с помощью прямого включения. Опираюсь на книгу 1989 года.
Код:
PROCEDURE StraightInsertion;
VAR i, j: index; x: item;
BEGIN
FOR i := 2 TO n DO
x := a[i]; a[0] := x; j := i;
WHILE x < a[j-1] DO a[j] := a[j-1]; j := j-1 END;
a[j] := x
END
END StraightInsertion
Cmin = n-1
Это я понимаю почему.
Цикл FOR выполнится n-1 раз и если элементы уже были упорядочены, то на каждом шаге будет выполнено только одно сравнение x < a[j-1] в цикле WHILE. Это условие будет равно FALSE сразу же. В итоге (n-1) * 1 = n - 1.
Но, скажем, каким образом Cmax = (n2 + n - 4)/4 остаётся для меня загадкой.
Понимаю, как считает тот же Левитин (Алгоритмы. Введение в разработку и анализ)
Двойная сумма сводится к одинарной. Ну а там арифметическая прогрессия...
Но как считает Вирт?