OberonCore https://forum.oberoncore.ru/ |
|
Подсчёт количества сравнений в АСД Вирта https://forum.oberoncore.ru/viewtopic.php?f=80&t=1932 |
Страница 1 из 1 |
Автор: | kemiisto [ Вторник, 06 Октябрь, 2009 23:17 ] |
Заголовок сообщения: | Подсчёт количества сравнений в АСД Вирта |
Здравствуйте! Не мог бы кто-нибудь объяснить каким образом в книге "Алгоритмы и структуры данных" подсчитывается количество сравнений для алгоритмов сортировки. Никак в толк не возьму. Скажем, сортировка с помощью прямого включения. Опираюсь на книгу 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 остаётся для меня загадкой. Понимаю, как считает тот же Левитин (Алгоритмы. Введение в разработку и анализ) Двойная сумма сводится к одинарной. Ну а там арифметическая прогрессия... Но как считает Вирт? |
Автор: | Algo [ Среда, 07 Октябрь, 2009 06:02 ] |
Заголовок сообщения: | Re: Сортировка. Подсчёт количества сравнений. |
Странно. Может опечатка. Ну ни как не может получиться ~ n^2/4. при i = 2 -> 2 сравнения, при i = 3 -> 3 сравнения, при i -> i сравнений, при i = n -> n сравнений. Получаем арифметическую прогрессию, начинающуюся с 2. Всего n-1 элементов. Сумма = Cmax = (n-1)(n+2)/2 = (n^2+n-2)/2. |
Автор: | kemiisto [ Среда, 07 Октябрь, 2009 13:31 ] |
Заголовок сообщения: | Re: Сортировка. Подсчёт количества сравнений. |
Algo, спасибо за ответ. Собственно, он по сути такой же как у Левитина. Просто у него индекс пробегает значения от 1 до n-1, а не от 2 до n. А вот как получилось Cmax = (n2 + n - 4)/4 ей богу не понятно. |
Страница 1 из 1 | Часовой пояс: UTC + 3 часа |
Powered by phpBB® Forum Software © phpBB Group https://www.phpbb.com/ |