Студопедия

КАТЕГОРИИ:


Архитектура-(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)

Пример медленного роста сложности в среднем в сравнении со сложностью в худшем случае




П

Y, у = In n + 0(1)

i =l


сложность T^in) можно записать в виде

Т}1(п)=(" + 4)("-1)-1пп + 0(1) (6.6)

[К 4 и, проще, в виде

Г; (п) = ^+0(п). (6.7)

п_2 4


Таким образом, сложность в среднем по числу сравнений первого ва­рианта сортировки простыми вставками, как и сложность в худшем случае, есть величина порядка п2, но при больших п первая слож­ность примерно вдвое меньше второй. Формула (6.6) показывает, что, вообще говоря, вопреки бытовым представлениям сложность в сред­нем не есть среднее арифметическое затрат в худшем и в лучшем слу­чае: такое среднее арифметическое для рассматриваемой сортировки является рациональной функцией от п и не может описываться этой формулой, содержащей логарифм.

Если рассмотреть вместо случайных величин Е}п, £2,..., Е^х слу­чайные величины г\\, г;2,..., rfn _1, соответствующим образом отража­ющие затраты исследуемой сортировки по числу перемещений, то, очевидно, будем иметь

^ *S r,j, *S?j, + 1,

i = 1, 2,..., n - 1. Поэтому сложность в среднем по числу перемещений

п2 тоже есть — +0(п). Нетрудно показать, что и сложности в среднем

по числу сравнений и числу перемещений второго варианта сорти­ровки простыми вставками равны — + 0{п). Сложность в среднем по суммарному числу сравнений и перемещений и для первого, и для второго варианта есть ^+0(п), поскольку для любых случайных величин Е,,г), определенных на каком-либо вероятностном простран­стве, выполняется

Е(? + т)) = Е? + Ет). (6.8)



Глава 2. Сложность в среднем


Каждая из сложностей в среднем как по числу сравнений, так и по числу перемещений для двух вариантов сортировки простыми встав­ками (всего четыре сложности) есть n + O{n); каждая из сложно­стей в среднем по общему числу сравнений и перемещений для двух вариантов этой сортировки (всего две сложности) есть n-+O(n).

Можно вспомнить, что в примере 1.4, в котором мы рассматрива­ли для двух вариантов сортировки простыми вставками их сложности в худшем случае по суммарному числу сравнений и перемещений, на­блюдалась непохожая ситуация, чему имеется, повторимся, простое объяснение: в отличие от (6.8), равенство шах(? + т?) = шах £ + шах tj, вообще говоря, места не имеет.

Общая формулировка установленного нами соотношения:

Теорема 6.1. Сложность в среднем некоторого алгоритма по сум­марному числу операций нескольких различных типов равна сумме сложностей в среднем этого алгоритма по числу операций каждого типа в отдельности.

Среди наиболее элементарных сортировок мы пока рассмотрели сложность в среднем только для сортировки простыми вставками. Сразу же можно добавить, что для сортировки выбором ее сложности по числу сравнений в среднем и в худшем случае совпадают, так как число сравнений однозначно определяется длиной n массива. Число сравнений на i -м этапе (i -м просмотре массива) пузырьковой сорти­ровки равно n — i. Не сталкиваясь с большими трудностями, можно показать (см. задачу 38), что математическое ожидание s{n) числа просмотров массива есть

k! kn~k n —

х—1 k k n ~ k

2_j ^Г~ • (6.9)

n!

k =o

Очевидно, что s(n)<n. С другой стороны,

у^ k! kn-k ху(n -1)! k _1у k _ n + 1
2-1 n! ~~~2-i n! n Zj 2 "

k =0 k =0 k =0

Поэтому s(n)^n -------- тг— = —Z-. Мы имеем

n -1

и s (n) =Θ(n). Из этого следует, что сложность в среднем по числу сравнений пузырьковой сортировки квадратична.

^s{n)<n


§ 7. Пример медленного роста сложности в среднем



Сложности в среднем по числу сравнений пузырьковой сортиров­ки, сортировок выбором и простыми вставками имеют одинаковый порядок со сложностями этих же сортировок в худшем случае (до­пускают оценку в(п2)).

Следующий пример показывает, что при п —> оо сложность в среднем может расти существенно медленнее, чем сложность в худшем случае.

Пример 7.1. Рассмотрим сложность в среднем fQS(n) быстрой сор­тировки по числу сравнений. Будем считать, что в качестве разбиваю­щего элемента всегда выбирается первый элемент сортируемой части массива. Введем случайную величину Е,п на П„, равную числу срав­нений быстрой сортировки для а е Пп (в этом смысле £п(а) = CTqs{a)).

Имеем

fQS(n) = E? n = ^y J] £п(а).

Введем разложение

Пп = Кп + Кп + --- + Кп>

где событию К1п принадлежат все те перестановки длины п, для кото­рых разбивающий элемент занимает i-ю позицию после завершения разбиения. В силу предложения 6.1(i) (видно, что К[ = FJ;1 событие состоит в том, что 1-й элемент перестановки равен i), получаем

Pп(7ф = -, i = l,2,..., п.

Разбиение перестановки а (первый этап быстрой сортировки) порож­дает две перестановки а'еП- и а"еП-. В соответствии с этим определим еще две случайные величины

£'п(а) = ^(аО, Оа) = C n - i f a "),

где i — номер позиции, которую занимает разбивающий элемент по­сле разбиения. По формуле полного математического ожидания




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


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


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



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




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