AOP_Tom3 (1021738), страница 199
Текст из файла (страница 199)
Обозначнм эту верхнюю оценку через е„(оз). Тогда г(й, т) = (л)/т)ев(гн). [В действительности такая функция г(2, т) не монотонна по оз, когда щ малб. Таким образом, элементы, перечисленные в табл. 2 для г(2,4) и г(2, 12), в действительности являются значениями г(2, 3) я г(2, 11). Дополннтельные буфера не могут увеличить число маркированных блоков,] 30.
Пусть ! = Ив + л/2зв) )п 3], а = л/2/з. Тогда ев(во)по) < )+ ~ 3(! з-а/3)' " /(1+ и)' с ' = ! + 3(1 + а/л)) ы ы в/а(1 + а) ' < )+ и ' ехр(()п3)(1+ ва — (в+ л/2в) )п(1+а))) н (в+ л/2зв))п(1+ а) > за+ 1 — а/3. Таким образом, 1 < г(3, вй)ой) = ев(зо )по) /2 1 / / 2 <1+)/ — + 1+)/ — )п3+0(в ()обЫ) )), — ! з в)пЫ )/в,йзв)п3~ Чйв еслн в/()об 3) -+ оо. Сходнмость этого аснмптотнческого выражения довольно слабая (см. табл. 2).
31. Когда 0 = О, маркируется первый блок н затем периодически маркируется следующнй блок, который разделяет диск с одним нз тех блоков, которые находятся в группе, начинающейся с ранее маркированного блока. Напрнмер, если хронологнческнй порядок обращения к диску — 112020121210122, маркировка будет иметь ввд 112020121210122, Таким образом, прн Р -+ оо считывается в среднем ле(0)п блоков в теченне и тактов времени, где )) — функция Раманьяна, определенная в соотношении 1.2.11.3-(2). И напротив, г(3,2) = (Ы + 1)/2 дает значительно более пессимистическую оценку.
РАЗДЕЛ 5.5 1. Трудно решить, какой алгоритм сиртнроекн наилучший в данной ситуации. 2 2. Прн малых )Ч нэнлучнзнм будет метод вставки в список; прн средних значениях )Ч, например прн Х = 64, — — метод слияния списков; прн большнх )Ч вЂ” метод поразрядной сортировки спнска. 3. (Решенне В. Пратта (Ч. Ргам).) Пусть заданы две неубывающие серии а н )з н нх нужно слить. Определим очевцдным способом подсернв азазаз)зз)ззДз~ такие, что аз и дз содержат в точности ключи нз а н )), имеющие медванное значение всего массива Выполнив "перебрасывание" подсернй, сформируем сначала алаз)ллз аз блаз, затем— я я а)близ ))з аз))з н, наконец, — азДзазфзазДз. В результате можно свести задачу к слиянию и к подлзасснвов ал))з н аз))з, имеющих длину < )Ч/2. Значительно более сложный алгоритм предложен Л.
Трабб Пардо (Ь. ТгаЬЬ Рагс)о). Этот алгоритм обеспечивает наилучший нз возможных резульзат в аснмптотнческом смысле. Можно выполнять устойчивое слнянне за время порядка 0()Ч) н сортировать за время порядка 0()Т!оЕХ), используя только 0(!оКХ) бит дополниаельной памяти для фиксированного числа индексных переменных, причем ие требуется никакого специального преобразования исходных данных [см.
Б!СОМР 6 (1977), 351-372]. Те же самые показатели по времени выполнения и объему памяти получены в работе В.-С. НвелЕ, М. А. Ьавбе1ов, Сашр. Х 35 (1992), 643-650. См. также А. Бупиов!з, Сошр. Х 36 (1995), 681-690, где описан метод устойчивого слияния М элементов в )Т, если М значительно меньше, чем )Т. 4. Только методы простой вставки, вставки в список и слияния списков. Некоторые варианты метода быстрой сортировки также можно сделать бережливыми, но только ценой дополнительных операций во внутреннем цикле (см. упр. 5.2.2 — 24).
Особое значение приобретают бережливые методы в том случае, когда результат сравнения обладает надежностью на все 100% (см. В. Е. КввсЬ, Еесгиге №гез ш Солар. Ясг. 606 (1992), .61-67). РАЗДЕЛ 6.1 ь '~ь'-аль .„~, ~ух-ов 2. Б1'. [Инициализацяя.] Установить Р +- Р1Е5Т. Б2! (Сравнение.] Если К = КЕТ(Р), алгоритм успешно завершается. БЗ( [Продвижение.] Установить Р +- 11ИК(Р) . Б4! (Конец файлау] Если Р ф й, перейти к шагу Б2'.
В противном случае алгоритм завершается неудачно. $ Время выполнения равно (6С вЂ” ЗБ + 4) и. 4. Да, если можно установить КЕТ(А) равным К. (Впрочем, метод дублирования цикла нз программы 1)' в этом случае не даст никаких преимуществ.) 5. Нет, программа Я всегда выполняет не меньше операций, чем программа Я'. 6.
Замените команды строки 08 командами ЮЕ а+4; СНРА КЕТ+И+2,1; 5ИЕ ЗВ; 1ИС1 1, а команды строк 03 н 04 — командами ЕИТ1 -2-И; ЗН ТИС1 3. 7. Заметьте, что ССИ = -'Сл-а + 1. 6. формула суммирования Эйлера дает !,) ... п~ * 1, Вгх а Бах(х+1) а г а „ И„' =0(х)+ — +- — — *+ (1 — х) 2 2! 3! (Из теории функций комплексных переменных известно, что С(х) = 2 я" 'в!п(-'ях)Г(1 — х)С(1 — х). Эта формула наиболее полезна прн х ( О.) 3. КЕТ ЕРС 11ИК Е00 ВТАЕТ АВА 101 2Н СНРА УЕ 101 71ИК РА110ЕЕ Е00 3:5 1:2 К РХКВТ 0,1(КЕТ) ВСССЕВИ 0,1(ЫИК) 20 в 1 1 С С С вЂ” Б С вЂ” Я 1 — Б 5 (Ь) С„з (1+Н/(1 — (л з))) з (Е/+Н'-з/Г(1 — 6)+Ц~О(л'-"). (с) При 6 < 0 (11) не является распределением вероятностей; (16) дает оценку Сл = — —,',зГ(1 — 8)/г'+" + О(гг' гз) + О(1) вместо (15) 10.
Рг « рл; (максимальное ССл) = (Л'+ 1) — (минимальное Сл) (Аналогячно в записях с переменной длиной максимальное среднее время поиска равно Ез(1+ рз) + .. + Вл(1 + рл) минус минимальное среднее время поиска.) 11. (а) Произведения / з(хн,,х,,)Р, представляют собой вероятности возможных последовательных запросов, после выполнения которых элемент К оказывается на пг-и месте. (Ь) Второе тождество получается после суммирования всех (") вариантов первого подмножества на различных гп-подмножествах Х с учетом того, что каждый нз них встречается Р4х раз. Третье тождество является результатом обращения второго.
(Можно также использовать пРннцип включениЯ и исключениЯ.) (с) ~ >огпР = гзгг'„— Я„1 зп а потому б, =1+(Н вЂ” 1) — Р.2 1 ,,Р+Р,' г( Рз + Рг ,с, Р + Рг Примечонне. В. Дж. Хегщрикс (ЪЧ. Л. НепбгЫгв) (Л. Арр!1сгЛ РгоЬаЫ1су 9 (1972), 231- 233) нашел простую формулу для финальных вероятностей каждой перестановки записей.
Например, прн Н = 4 предельная вероятность последовательности йзНг Нз Е7г равна 1г г Р4 Рг рз Рз+Рг+Рз+Рг Рг+Р4+Рг Р4+Рг Рг Джеймс Битнер (Лашез Вппег) (лЕСОМР 8 (1979), 82 — 85) доказшд что, если изначально список неупорядочен, ожидаелгое время поиска после Г случайных запросов превысит Сл на величину -„' 2', .(р,— р )г(1-р, -р,) /(Р,+Р,). Таким образом, для Г поисков потребуется в среднем менее ГСл + -'Е,',,(Р, — р,) /(Рг + Р,) < 1Сл + -'(г) сравнений См. также доказательство с применением производящих функций в работе Р. г!аЛо!ег, ГЛ Оагбу, авб 1..
ТЫгггопгег, О!Ясгезе Аррйгб Магрь 39 (1992), 207-229, 56. 12. ССл = 2 ' + 22 „:е 1/(2" + 1) Это выражение быстро сходится к 2п' 2.5290: в упр. 5 2 4-13 дано зйаченне и' с точностью до 40 знаков. 13. После выполнения весьма утомительного суммирования п(я+ 1)(2гг-г 1) п(п+ 1)(10п — 1) ге 6 36 ь=! получим ответ: Сл = зН з(2Ж ' 1)(ЕЕг" Н') + (Ж Ч 1) 409% 14.
В предположении, что хг < хг « . х„максимальное значение достигается при у, < у, « у „и минимальное — прн у, » .. у „. Рассуждения аналогичны рассуждениям при доказательстве теоремы Я. 15. Рассуждая так же, как в теореме Б, можно прийти к выводу, что расположение Нг Нг... Вл оптииально тогда и только тогда, когда Рз/Ег(1 — Рг) » ... Рл/Е,л(1 — Рл). 16. Ожидаемое время проверкиТс+рсТг+рсргТг+ +ргрг - рл сТл минимально тогда и только тогда, когда Тг/(1 — рс) « Тл/(! — рл) (В!Т 3 (1963), 255-256; некоторые интересные дополнение получены Джеймсам Р. Слейглом (!алиев Н. Исай)е), ЗЛСМ 11 (1964) 253 2641 17. Выполняйте задания в порядке увеличения их крайних сроков выполиеаия — - независимо от значений Т!! (Естественно, в реальной жизни одни задания важнее других и требуется минимизировать максимальное взвешенное запаздывание; возможно, придется минимизировать сумму 2 ",, шах(Т„, + +Т г — Р,„О).
Похоже, однако, что простого решения для таких постановок задач не существует.) 18. Положим Ь = 1 при наличии в и Ь = О в противном случае. Пусть Л = (! ~ 9, < гг), В = () ) д, = г,), С = (! ! дг > г,), Р = (! ! С, > 0); тогда сумма 2„,, р,ргйл, для расположения (9, г) минус соответствующая сумма для расположения (9',г!) будет равна 2 ~ (д, — гс)(9г — г,)(4ч,! — с!лег ы, г)+2 ) (у, — г )С,(А„.гл,е! — сс, ьы). ЕА,уЕС ЕС,геа Эта величина положительна, за исключением случаев, когда С = 9 или АсгР = 9. Искомый результат следует из того, что расположения в виде "органных труб" — единственные расположения, которые не могут быть улучшены таким способом (и с помоосью его зеркального двойника) при го = О, 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
