О сортировке, оптимальной по числу сравнений в худшем случае

Со

T со

GO fc CO fc CO

Fc со fc

Об одном свойстве сумм неотрицательных случайных величин

Здесь доказывается теорема 17.1 из § 17.

Пусть £,_ъ?_2> ••• —последовательность неотрицательных случай­ных величин на некотором вероятностном пространстве. Пусть чис­ловая последовательность h_ъh₂,... такова, что для каждого k ^l выполнено EC^ _k ld,?2, •••> S _k -i) ^ h при всех значениях Е,ъ?₂, •••, S _k -i. Зафиксируем неотрицательное число q и введем целочисленную слу­чайную величину

T = min n: ^ £ _k ^ q L

k =1

Пусть τ< ∞ всюду на рассматриваемом вероятностном простран-

стве. Тогда E £ h k ^ q.

k =l

Рассмотрим случайные величины j _k, k = 1, 2,..., где Ji = 1, а при k > 1 выполняется j _k = 1, если ^ + £₂ +... + ^ _k -_x < q, и j _k = 0 в про­тивном случае. Заметим, что

_ (1, если т^k, ^Х_k~0, еашт<k,

и l=_Xl^_X2^...

Положим p_k = P(т = k) = P(.х_k = 1) - P(.Xk+i = D, k = 1, 2,... Ясно, что P(* _k = l) = l- p i- p ₂-...- p_k -i. Имеем

о» k

'—■■ k =i j =i GO ^(P(_{J k} = l) - P{xk+i = D) Xi hj

k =l k =l j = \

k

= P^ _k =-LJ - PU _k +l =

k =l j =l

234 Приложение Е

со к со к

= ^ P(_Jfc = 1) ^ hj - Y, P(jfc+i = 1) Xi h i =

fc=l j =l fc=l j =l

соfcсоfc -1

= 2 P(_Jfc = 1) Xi h i - 2 P(*^fc = 1^} 2 hi =

k=l j = l k=2 j = l

^ P(_Jfc = 1) ^ hj - X P(jfc = 1) X ^ - h fc

fc=l j = \ fc=2 j = l

= J^ PiXk = 1) X h i -2 P(*^fc = 1^} 2 h i +2 P(-^Xk = 1) h ^fc =

fc=l j = l fc=2 j = l k =2

GO

k =2

=x h fcP(^ = 1)-

fc=l Таким образом,

EfXi h 0 = 2 h ^fcP (^ = ⁱ) - (e.ⁱ)

fc=i fc=i

Введем случайные величины rj_fc = *_fc£_fcД = 1, 2,...; из определения случайных величин j_fc следует, что

Y^Vk^q- (E.2)

fc=i

Докажем, что для fc = 1, 2,...

E^_fc^?ifcP(jfc = l)- (E.З)

Рассмотрим полную группу событий W_lt W₂: в W _x попадают те элемен­ты вероятностного пространства, для которых Е,_г + Е,₂ + ••• +? k -i < <L в W₂ —для которых Е,_г + Е,₂ + ••• +?fc-i ^ <?. С учетом определения слу­чайной величины j_fc, равной 1 на множестве Ш_г и 0 на множестве W ₂, получаем по формуле полного математического ожидания:

= E0r_fc?_fc| W i)P(W i) + E(j_fc?_fc| W ₂)P(W ₂) = = E(?_fc| W i)P(W i) = = E(?_fc| W ₁)P(j_fc = l),

Об одном свойстве сумм случайных величин

т. е.

ET}_fc = E(?_fc| W 1)P(jr_fc = 1). (Е.4)

Так как по условию неравенство E (^_к|^₁, Е,₂,...,? k -1) ^ h_k выполня­ется при всех значениях Е,₁, Е,₂,...,?fc-1> то оно выполняется на W₁. С учетом (Е.4) имеем E(?_fc| W 1)P(*_fc = 1) s= h_k, откуда следует (Е.З). Из (E.I), (Е.2), (Е.З) получаем

GO GO со %

q = E q ^E[2^T) k l=2E^T'*^<2 h ^fcP(*^fc = 1) = E(2 h 0,

4=1 fc=1 fc=1 4=1

что и требовалось¹.

¹ Сходное, но менее подробное доказательство имеется в [2, гл. III, § 5, теорема 1], но там в условии теоремы пропущено требование конечности т (см. задачу 96).

Приложение F

Долгое время считалось правдоподобным предположение, что сорти­ровкой, оптимальной по числу сравнений в худшем случае, является сортировка бинарными вставками, о сложности Т_в(,п) которой, вме­сте с этим, было известно, что Г_в(5) = 8, при том, что наибольшая из обоснованных нижних границ для числа сравнений, необходимых для сортировки пяти элементов, есть [log₂5!] = 7. Это порождало ги­потезу, что сложность T _opt(n) оптимальной сортировки для некоторых значений п больше, чем [log₂ n!l, и первое такое значение п равно пяти. Но в 1956 г. Г. Б. Демутом был найден алгоритм сортировки пяти элементов, который требует всего семь сравнений.

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

а потом сравниваем меньшие найденные

м

'< ------- •< -------- • элементы; на это уйдет три сравнения

(рис. 28). Этим, в частности, для трех эле­ментов из пяти мы устанавливаем их отно­сительный порядок. Затем для пятого эле­мента, который еще не сравнивался, мы на-

_Рис лементов: _тир ит _овка а™ ходим место среди трех уже упорядочен-
после трех сравнений ных элементов бинарным поиском; на это

уйдет два сравнения. Тем самым мы прихо­дим к одному из двух случаев, изображен­ных на рис. 29. И в том, и в другом случае для завершения сор­тировки с помощью бинарного поиска места элемента достаточно двух сравнений: в случае, изображенном на рис. 29а, вставка про­изводится в массив из двух элементов, в случае, изображенном на рис. 29б, — из трех элементов. В итоге семи сравнений оказывается достаточно.

О сортировке, оптимальной по числу сравнений

а)

б)

Рис. 29. Сортировка пяти элементов, ситуация после нахождения места пято­го элемента среди трех упорядоченных элементов: а) пятый элемент меньше всех трех упорядоченных элементов; б) пятый элемент больше наименьше­го из трех упорядоченных элементов. (В обоих случаях еще двух сравнений достаточно для завершения сортировки.)

Указанный алгоритм сортировки пяти элементов был позднее обобщен на произвольное число элементов, эта сортировка получи­ла название сортировки слияниями и вставками. Через T _F(n) обыч­но обозначается сложность этой сортировки по числу сравнений. Обнаружено, что T _F(n) = [log₂ п!1 для п = 1,2,...,11. Но при этом Гр(12) = 30, хотя [log₂ 12!] =29, и возникает вопрос, всегда ли воз­можна сортировка двенадцати элементов не более чем двадцатью де­вятью сравнениями? Аналогичные вопросы могут возникнуть и для больших значений п.

Как говорилось в § 14, имеется алгоритм, который, исходя из п > О, строит оптимальный по числу сравнений алгоритм сортировки мас­сивов из п элементов (алгоритм строит алгоритм). Этот алгоритм построения оптимального алгоритма сортировки требует огромной работы, даже если применить все средства экономии перебора. Но, тем не менее, на этом пути с помощью компьютера показано, что Г_орД12) = 30, что больше, чем [log₂ 12Г|. Но дальше продвинуться не удалось, и по сегодняшний день, видимо, неизвестно число T _opt(13):

п: 1 2 3 4 5 6 7 8 9 10 11 12 13

[log₂ n!l: 0 1 3 5 7 10 13 16 19 22 26 29 33

Т_в(п): 0 1 3 5 8 10 14 17 21 25 29 33 37

Г_Р(п): 0 1 3 5 7 10 13 16 19 22 26 30 34

r_opt(n): 0 1 3 5 7 10 13 16 19 22 26 30?

Исследования, не связанные с компьютерным вычислением T _opt(n), показали, что имеется бесконечно много значений п, для которых T_F(n)>T_opt(n). Значение 47 —наименьшее из известных¹.

См. [20, разд. 5.3.1].

Приложение G

Дата добавления: 2014-01-11