OberonCore

Библиотека  Wiki  Форум  BlackBox  Компоненты  Проекты
Текущее время: Понедельник, 17 Декабрь, 2018 20:02

Часовой пояс: UTC + 3 часа




Начать новую тему Ответить на тему  [ Сообщений: 3 ] 
Автор Сообщение
СообщениеДобавлено: Вторник, 06 Октябрь, 2009 23:17 

Зарегистрирован: Воскресенье, 03 Февраль, 2008 12:50
Сообщения: 232
Здравствуйте!

Не мог бы кто-нибудь объяснить каким образом в книге "Алгоритмы и структуры данных" подсчитывается количество сравнений для алгоритмов сортировки. Никак в толк не возьму. :oops:

Скажем, сортировка с помощью прямого включения. Опираюсь на книгу 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 остаётся для меня загадкой. :shock:
Понимаю, как считает тот же Левитин (Алгоритмы. Введение в разработку и анализ)
Изображение
Двойная сумма сводится к одинарной. Ну а там арифметическая прогрессия...

Но как считает Вирт?


Последний раз редактировалось kemiisto Среда, 07 Октябрь, 2009 13:47, всего редактировалось 1 раз.

Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Среда, 07 Октябрь, 2009 06:02 

Зарегистрирован: Воскресенье, 08 Март, 2009 17:54
Сообщения: 372
Странно. Может опечатка. Ну ни как не может получиться ~ 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.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Среда, 07 Октябрь, 2009 13:31 

Зарегистрирован: Воскресенье, 03 Февраль, 2008 12:50
Сообщения: 232
Algo, спасибо за ответ. Собственно, он по сути такой же как у Левитина. Просто у него индекс пробегает значения от 1 до n-1, а не от 2 до n. А вот как получилось Cmax = (n2 + n - 4)/4 ей богу не понятно. :(


Вернуться к началу
 Профиль  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 3 ] 

Часовой пояс: UTC + 3 часа


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 1


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Вся информация, размещаемая участниками на конференции (тексты сообщений, вложения и пр.) © 2005-2018, участники конференции «OberonCore», если специально не оговорено иное.
Администрация не несет ответственности за мнения, стиль и достоверность высказываний участников, равно как и за безопасность материалов, предоставляемых участниками во вложениях.
Без разрешения участников и ссылки на конференцию «OberonCore» любое воспроизведение и/или копирование высказываний полностью и/или по частям запрещено.
Powered by phpBB® Forum Software © phpBB Group
Русская поддержка phpBB