Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Оценка трудоемкости сортировки




Вставка и удаление в сортированной таблице

 
 

При вставке новой записи в сортированной таблице, требуется найти место в которое её следует поместить (время ~ ) и сдвинуть все записи от места вставки и ниже на одну позицию вниз. Аналогично, при удалении требуется найти удаляемую запись и все записи ниже удаляемой сдвинуть на одну позицию вверх. Обе операции требуют физического перемещения в среднем записей. Таким образом, при таком простодушном поведении, мы проигрываем все преимущества сортированной таблицы для операции поиска. Поэтому при удалении запись не удаляют физически, а лишь помечают как удаленную в специально отведенном байте. При вставке находят ту позицию, в которую следовало бы поместить новую запись, чтобы она не нарушала порядка, но не помещают ее туда, а помещают в линейный список,

начинающийся с позиции вставки, как на рис.31.

Рис.31. Сортированная таблица с цепочками переполнения

При поиске записи теперь следует найти позицию, в которой должна была бы находиться запись и, отправляясь от нее пройти линейный список, исходящий из этой позиции. Очевидно, что после большого количества вставок, поиск будет все больше походить на простой перебор записей. Рано или поздно, придется переписать таблицу как сортированную заново, таким образом, чтобы в ней не было удаленных позиций и цепочек переполнения. Отложенные операции обслуживания характерны для всех способов организации таблиц, кроме древовидных.

Оценим трудоемкость процесса упорядочения массива из N ключей. В исходном состоянии эти ключи могут образовывать любую из N! перестановок. Энтропия массива ключей, определяемая по Шеннону:

где pi – вероятность перестановки с номером i. Наибольшей энтропией обладает система, для которой все состояния равновероятны: . Для упорядоченной таблицы, все ключи которой различны, энтропия равна нулю. Изменение энтропии равно количеству информации, получаемой в процессе сортировки. Для случайного массива необходимо получить бит информации. При сравнении ключей Ki, Kj можем получить два исхода: Ki<Kj и Ki>Kj. (случаем Кi=Kj пренебрегаем, как маловероятным).

Если исходы равновероятны, то сравнение дает ровно 1 бит информации. Такие ключи называют статистически эквивалентными. Если исходы неравновероятны, то будет получено меньше одного бита информации. Кстати, именно из-за того, что некоторые сортировки сравнивают статистически неэквивалентные ключи, они имеют низкую эффективность.

Таким образом, число сравнений ключей при сортировке удовлетворяет неравенству

Для вычисления N! воспользуемся формулой Стирлинга

С учетом этого после преобразований получим

Найденная оценка будет служить ориентиром при оценке эффективности различных методов сортировки.




Поделиться с друзьями:


Дата добавления: 2014-12-08; Просмотров: 1394; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.008 сек.