AOP_Tom3 (1021738), страница 205
Текст из файла (страница 205)
(Индекс ММ означает нижний левый угол матрицы.) Теперь И' = Я 1 ейаб (Л»,, Лм) Я для некоторой матрицы з, где ейай (Л»,, Лм) обозначает диагональную матрицу, элеиентами которой являются корни полинома )((Л) = (Л+ 2)... (Л+ М+ 1) — (М+ 1)(. (Все корни различны, поскольку х(Л) = Л'(Л) = 0 приводит к 1/(Л+2)+ -(-1/(Л+М+1) = 0; это может выполняться только тогда, когда Л действительно и — М-1 < Л < — 2, откуда вытекает, что )Л+2(... (Л+М+1/ < (М+ 1)!, а это противоречит начальному условию.) Если р(х) — некоторый полинам, то р(И) = р(Я »баб(Лц...,Лм)а) = Б 'б!аб(р(Л1),...,р(Лм))Б; следовательно, правый нижний элемент р((4) имеет вид с»р(Л1)+ +смр(Лм), где некоторые константы см..., см не зависят от р. Эти константы мшкно вычислить, положив р(Л) = Л(Л)/(Л вЂ” Лг); так как ()4'~)»гм = ( — 2)» при0 < Л < М-1, имеем р(!4')мм = р( — 2) = (М+1)!/(Л,+2) = с;р(Л,) = сгт'(Л!) = сз(М+ 1)$(1/(Лг+ 2) +.
+1/(Лг+М+1)). Значит, сг = (Л!+2) '(1/(Лг+2)+ + 1/(Лг+ М+ 1)) . Это дает "точную" формулу С» — — 2™, гсг/в(Лг); остается только исследовать корни Лз. Заметим, что (Л + М + Ц < М + 1 для всех /, иначе мы бы имели (Лг + 2(... (Л! + М+ Ц > (М + 1)!. Взяв Л» — — О, убеждаемся, что Я(Лг) < 0 для 2 < / < М. Согласна 1.2.5-(15) д„(х) (и+ 1)*/Г(х+ 2) при и -+ оо; следовательно, д„(Л ) -+ 0 для 2 < / < М.
Таким образом, С,',. = 2с, /л (0) + 0(1) = Нк/(Нм», — 1) + 0(1). Примечание. Приведенный анализ применим также к алгоритму простой сортировки, вкратце обсуждавшемуся в разделе 5.2.2. Вычисления могут быть легко дополнены для того, чтобы показать, что Ив0!(1) (Нм»г — 1) '/(/+ 2) при 1 <,г < М и В~~„: (1) (Нм+1 — 1) '/2. Поэтому общее количество внутренних узлов в незаполненных страницах приблизительно равно ( .
/.„- -('- З х г + 4 х З + + (М+ Ц х М/ И,„., — 1 (~ (М+ 1)(И „— 1) /' ' а общее количество использованных страниц примерно равно ( 1 1 1 1 Лг !Лг — + — + + + Зх2 4хз (М+ 1) х М М+1/ Нм»» — 1 2(имм — 1) откуда следует, что асимптотическое использование памяти равно 2(Нмх1 — 1)/М. Этот анализ был развит в работе Махмуда (МаЬшоа»!) и Питтеля (Р!гсе!) (,Л А!Богибп»в 10 (1989), 52-75), которые открыли, что дисперсия количества использованной памяти подвергается неожиданному фазовому переходу: при М < 25 дисперсия равна сг(Х), но при М > 26 ана асимптотически равна /(Х)?»г™, где /(е" ~В?»г) = /(!»Г), если --'+ а+ Б! и — -' + а — Б! являются ненулевыми корнями Лг с наибольшей действительной частью.
Высота таких деревьев проанализирована в работах П Пе»гоуе, Иалг!ош Бсгасввгев апд А18оНГИшв 1 (1990), 191 — 203, и В. Р!Ые!, Вапггош Бсгосспгвв аас! А!доНГИтв 5 (1994), 337-347. 9. Да; например, мы могли бы заменить каждое К, в (1) на» плюс число ключей в цоддеревьях ра,,р, ь Соответствующим образом изменяются алгоритмы поиска, вставки и удаления. 10. Краткий набросок; расо»прим страничную схему так, чтобы исключительный доступ к буферам предоставлялся талька одному пользователю одновременно. Алгоритмы поиска, вставки и удаления должны быть тщательно модифицированы, чтобы такой исключительный доступ предоставлялгя только на ограниченное время, только при крайней необходимости и таким образом, чтобы не возникало клинчей.
За подробностями обратитесь к работам В. Башаг)1, Упб Ргос. Ъеггегв 5 (1976), 107-112; В.. Вауег авб М. БсЬЬо!и!сЬ, Асга !лб 9 (1977), 1-21; г'. Баб!», Х Сотр. Бувг. Боб 33 (1986), 275 — 296. РАЗДЕЛ 6.3 1. Отблески. (На самом деле перед нами непереводимая игра слов, основанная на близости слов !гве и !г!е. В связи с этим ниже приводится текст оригинала упражнения и ответа к нему. — Прим. перев.
П а ггее Ьвв !еа»ев, »»Ьав г(сев а !г!е Ьа»е? 1ле»ев (ГЬе р1цга! а( "1!ебм).) 2. Выполните алгоритм Т, используя в качестве аргумента новый ключ; поиск закончится неудачно на шаге ТЗ или Т4. Если последний шаг — ТЗ, просто поместите К в элемент таблицы НООЕ(Р) с номером А и завершите работу алгоритма. В противном случае поместите в эту позицию адрес нового узла Ц ~ АУА11, содержащего пустые ссылки, а затем установите Р +- Ц.
Теперь присвойте й и й' соответственно гледующие символы К и Х: если й ф /с', сохраните К в позиции А узла 8098(Р), а Х вЂ” в позиции Ь'; однако, если А = А', поместите в позицию А указатель на новый узел Ц ~ АЧА1Ь и присвойте Р ь- Ц. Повторяйте этот процесс до тех пор, пока не получится Ь эс А~ (считается, что ни один из ключей не служит началом другому). 3. Заменим ключ пустой ссылкой в том узле, в котором он находился. Если таперь данный узел стал "бесполезным" в силу того, что все его элементы, кроме одного, представляющего ключ Х, пусты, удалим этот узел и заменим соответствующий указатель в родительском узле указателем Х.
Если "бесполезным" становится родительский узел, удалим сто описанным способом. 4. Успешный поиск будет проходить так же, как и в случае несжатой таблицы, однако для неудачного поиска в сжатой таблице может потребоваться несколько дополнительных итераций. Например, такой аргумент поиска, как ТЕАЗН, заставит программу произвести шесть итераций (что явно больше пяти!); этот случай является наихудшим. Необходилсо также проверить невозмохсность зацикливания на пустых позициях.
(Этот замечательный пример упаковки таблицы в 49 элементов предложен Дж. С. Фишберном (3. Ясос Р'сэЬЬпгп), который также доказал. что 48 позиций для упаковки таблицы недостаточно,) Ьолее медленный, но более многосторонний путь экономии памяти для луча был предложен Куртом Мали (Кнгс Ма)у), САСМ 19 (1976), 409 — 418 В общель если нухсно сжать и разреженных таблип, содержащих соответственно хн ..., х„ненулевых элементов, метод 'первый подходящий", который смещает )-ю таблицу на минимальную величину г, с целью избежания конфликтов с ранее размещенными таблицами даст гэ < (хс+ .. + хс с)х„, поскольку каждый предшествующий ненулевой элемент может блокировать не более х) смещений.
Такая оценка наихудшего случая дает г) < 93 для табл. 1, гарантируя, что любые 12 таблиц длиной 30, содержапсие соответственно 10, 5, 4, 3, 3, 3, 3, 3, 2, 2, 2, 2 ненулевых элементов, могут быть упакованы в 93+ 30 последовательных позиций безотносительно к двоичному представлению ненулевых элементов. Дальнейшее усовершенствование этого метода было проведено в работе В. Е. Тат)ап апс1 А. С. Уао, САСМ 22 (1979), 606-611. Динамическая реализация сжатых лучей, предложенная Ф. М. Лиангом (Р. М. 1Лапб), использована в таблицах переносов в издательской системе ТЕХ (см.
В. Е. КппсЬ, САСМ 29 (1986), 471-478; Рйсегасе Ргобгвшт(лб (1991), 206-233). б. В каждом семействе сначала проверяется наиболее вероятный исход; для этого буквы располагаются слева направо в порядке уменьшения вероятности. Оптимальность такого упорядочения может быть доказана аналогично теореме 6.15.
(См. САСМ 12 (1969), 72-76.) л ч е йь Н ьй й 8 Н «8 ч ч е й й ь ч И й Я 7. Например, Е, 4, 1, 2, 3, 5 6, 7, 12, 9, 10, 11, 13, 14, 15. (Независимо от того, какая последовательность используется, ни левое, ни правое поддерево не может содержать болыпе двух узлов на уровне 4.) Даже полученное нами "наихудшее" дерево принадлежит к числу четырех каплуна~их возможных деревьев, так что, как видите, деревья цифрового поиска ие слишком чувствительны к порядку вставки.
Н. Да. В поле КЕУ теперь содержится только усеченный ключ; левые биты„значения которых определяются позицией узла, удалены. Аналогичная модификация применима и к алгоритму Т. т. и .. (х=г) Р ~ — ЕНОТ. (г11 = Р) Время работы фазы поиска этой программы равно (10С вЂ” ЗЯ+ 4) и, где С вЂ” Я представляет собой число проверок битов. Для случайных данных приближенное среднее время работы таково.
Успешно Неудачно Программа 6.2.2Т 15 !и Лг — 12.34 15 1и )У вЂ” 2. 34 Данная программа 14. 4 1и !У вЂ” 6. 17 14.4 !и Лг+ 1.26 (Следовательно, при не очень больших Л' программа 6.2.2Т работает несколько быстрее,) 10. Обозначим через 9 операцию "исключающее или" над и-битовыми числами, и пусть 7(х) = и — (!К(х + 1)1 — число левых ненулевых битов х. Вот одно из решений: (Ь) если поиск с помощью алгоритма Т заканчивается неудачно на шаге ТЗ, то А на единицу меньше количества проверенных битов; в противном случае> если поиск заканчивается на шаге Т4, А = У'(К Ю Х). (а, с) Выполним обычный поиск, но при этом будем хранить х— минимальное значение К Ю КЕУ(Р) по всем КЕУ(Р), сравнивавшимся с К в процессе поиска.
Тогда А = 7'(х). (Докажите, что наибольшее число битов, совпадающих с К, имеют ключи, сравниваемые с аргументом. В случае (а) максимум А достигается либо для наибольшего ключа ( К, либо для наименьшего ключа ) К.) 11. Нет; удаление узла только с одним пустым поддеревом приведет к потере одного бита в ключах непустого поддерева.
Для удаления узла следует заменить его одним нз 9. ЕУАНТ 10х к 101 НООТ ЭМР 2Р 4Н 602 0,1(51.1МК) 122 5Р 1н емт1 о,г 2Н СНРХ 1,1 )Е БОССЕББ 51.В 1 )АО 4В 502 0,1(ШМК) 12МХ 1В ЕН Продолжение то 1 1 1 С2 С2 С вЂ” 1 С С С вЂ” л С вЂ” Я С1 С1 же, что 04. Пе еме ение еп аво. Ц ~ — НЬ1МК(Р). Переход к шагу ))5 при Ц = Л. Р е — Ц Р.с Выход при К = КЕУ(Р) . Смещение К влево на один бнт. Переход к шагу О4, если выделенный бит равен 1. 03. Пе еме ение влево. Ц+- 1.1.1МК(Р). Переход к шагу Т)2 с Р < — Ц, егли Ц ,-4 Л.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
