Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 2) (1119371), страница 97
Текст из файла (страница 97)
Здесь Х~ есть число "инверсий с равенством" в тп а именно — )(г ! г > 1 и 1, < 1~)(, т, е. число заполненных буферов, в которые мы считали информацию, но еще не готовы ее использоватги В представляет буфера, в которые будут считываться следующие исходные данные, и Р -- частично заполненные буфера, нз которых берутся данные для слияния. (Приняв некоторые специальные меры, можно, используя связи, как в случае с алгоритмом 8ув<8огс, ослабить последнее требование с Р до Р— 1, но усложнение процесса, которое прн этом происходит, вряд ли сделает такую операцию целесообразной,) Таким образом, проблема сведена к определению верхней оценки Хь Можно предцоложить, что входные серии имеют бесконечно большую длину. Предположим также, что з в элементах (1м...,1~) болыие, чем 16 тогда 1~ имеет 1~0 — 1+ з инверсий с равенством, поскольку точно 1~0 элементов < гь Отсюда следует, что максимум Х~ получается, когда з = О и 1~ есть максимум слева направо.
Имеем 2'ь, вм = 1; значит, учитывая приведенные выше формулы, для 1~ получаем Х~ < шах(1~0 — 1) < Х (им — (8 — хь) шобВ+  — 1 — им) юг ь 1 Р = Р(0 — 1) — ~~ (Н вЂ” хь) шобВ < Р(Р— 1) — сош "~ (8 — хь) шобР о<к<о ь=1 и существуют хронологические порядки, для которых достижима зта верхняя оценка. Предположим, что г~ из гь равны 1. Желательно выбрать хь таким образом, чтобы максимизировать пнпойз<о зш где зз = Х ь,(д — хь) шоб В = 2 „„((я — 1) шац В)гь Можно предположить, что минимум будет при 8 = О. Тогда з~ = зо + Р— ОР, зт = з~ + Р— гзР,....
Отсюда получаем г~ < (Р/В), с~ + гт < (2Р/В),..., поэтому минимумом о — ) зо = ( — 1)ш +( — 2)ге+ +го-~ < ЯЯР~В) = -((Р— 1)(0 — 1) +8<6(РР) — 1), 1 2 что вытекает из результатов упр. 1.2.4" 37. Эта граница достигается, когда хз = (ХРХ Р) — 1 при 1 < у < Р. Имея такое х,, можно работать с любой хронологической последовательностью па полной скоРости„если в нашем РаспоРЯжении есть Хм,„+ В + Р = -'РВ + зВ+ -'Р + 18сб(Р, В) — 1 входных буферов, в каждом из которых отведено место для В записей. (Это особенно хорошо, когда В = 2 или 3.) 26. Обратите внимание на то, что в цикле 4 мы возвращаемся к чтению /, с диска О.
Активные чтения Активные слияния П1ючие В ожидании Ци кл 1 еоЬеуеаосе — — — — — — — — ( — — — — — — — ) ое Цикл 2 /аз(оа(аа(г/о ое- — — — — — — Ьесе(евдо- — -) а(е Цикл 3 егйоегдаа(з ообосеа(е — — — — ее/еде(а(за(з/а — ) Ьз Цикл 4 /аеабадаоа ообесоооее/еде)ао а)а(а(гега(з/адгог) еа Цикл 5 аг/гйгездг ообесеа(аеа/еуойе а(гага(зоа/а ба да о ог Цикл 6 аСаез/збгеа огЬасоа)зег/адайе /гез(Ьауг — — — ) а(а Цикл 7 сааз/з 7 еа агбасоа(асз/гдгйе (бабадгоз/зеа -) са Цикл 8 а(за(з 7 7 агЬ, са а(аез /гдаЛе 5 аЬг дгаз /зеа ( '.
) а(з 26. В то время, когда В блоков считываютсл и В блоков записываются, процедура слияния могла бы сформировать до Р + Π— 1 блоков на выход, предполагая выполнение схемы (24). (Но не Р + О, поскольку тачько один буфер слияния будет абсолютно пуст,) Считывавне выполняется с той лае скоростью, что и запись„а потому необходимо В + Р+ б) — 1 буферов вывода для предотвращения задержки вывода. Однако в среднем не более В блоков явлюотся выводными для келалых входных В блоков, так что на пршатике нужно ориентироваться приъаерно на ЗВ выходных буферов. 27. (а) Ее(та,..., тр) = Яа а уа, где у, есть вероятность того, что в некоторой урне содержится не менее С шаров. Очевидно, что ф < 1 и уа < ~~а Рг(урна Ь содержит не менее С шаров) = таРг(Я„(та,...,тр) > С).
(Ь) П1зоизводящан фу'нация ве1гоятностей для Я (гпа,..., из„) такова; р(з) = П раз(1+ (з — 1)гз/и), где уз = (пзз/и) и гз = тз шобп. Теперь 1+ о < (1+ о/и)" и 1+ ар/и < (1+ а/и)", когда о > 0; отсюда имеем Рг(о„(та,..., тр) > С) < (1+ аз) 'р(1+ и) < (1 4 ж) ' П„",(1+ и/п)м" (1+ и) '(1+ а/п)~.
если с < т/и, используется член "1" в сформулированном минимуме. если с > гп/и, величина (1+ и)"'(1+ и/и)™ принимает минимальное значение (и-1)' 'т™/(пшза(гав С)~ '), когда а = (пз — т)/(гп — С). 28. Как нам кажется, числовой подсчет подтверждает зто предположение. Например, получим = 1.98, = 1.94, = 1.7, = 1.7, = 1.7, = 1.7. 29. (а) В момент С со всех дисков считываются блоки, которые появятся не ранее, чем блок, маркированный в момент С, Следующие О блоков никогда не будут удалены из группы прочих буферов, если они прочитаны.
Таким образом, интересующие нас блоки на Ещ(1,1, 1, 1, 1, 1, 1,1) = 2.3993180, Ею(2, 1, 1, 1, 1, 1, 1) = 2.364540, Еае(2,2.1,1,1,1) = 2.32076, Еае(3, 1,1,1, 1,1) = 2.29958, Еао(2,2,2,1,1) = 2.2628, Е (3,2,1,1,1) ш2.2460, Еас(4, 1,1, 1, 1) = 2.2076, Ею(2,2,2,2) = 2,178, Еас(3, 2, 2, 1) = 2.166, Еае(З,З, 1, 1) = 2.152, Еао(4,2, 1, 1) = 2.138, Еае(5,1,1,1) = 2,090, Еае(3, 3, 2) = 2,02, Еае(4,2,2) = 2,01, Е (4,3,1) Его(5, 2, Ц Еае(6, 1, 1) Еао(4,4) Еае(5,3) Еае(6, 2) Еае(7, 1) диске / будут считаны во время < ! + Л'„все они должны принять участие в слиянии во время !+ шах(Фо,...,Зуо-з). (Ь) Если (!г'+ 1)-й блок после маркированного блока не удален, то поясно использовать тот же аргумент В проз пеном случае предыдущие Ц не маркированы и Я+ 2 блоков не могут размещаться на разных дисках.
(с) Разделите хронологический порядок блоков на группы размером Ц + 2 и рассмотрите любую из ннх. Если существует Мг блоков вз серии й, то числа !Э!з эквивалентны числу взаров в гзй урне в задаче о циклической занятости прн и = 1:г и гл = Я + 2. Таким обрезом, ожидаемое число маркированных ячеек не превышает верхней оценки в упр. 27, (Ь). Обозначим эту верхнюю оценку через е„(гя). Тогда г(з1, т) = (з(/гл)св(ш) (В действительности такая функция г(2, гл) не монотонна по гл, когда гл малб. Такилз образом, элементы, перечисленные в табл.
2 для г(2,4) и г(2,12), в действительности являютсл значениями г(2, 3) н г(2, П). Дополнитеззьные буфера не могут увеличить число маркированных блохов.) 30. Пусть ! = ((в+ э/2вв) 1пз!1, о = э/2/в, Тогда ев(вз(1вй) < !+ ) з((1 а а/з!)"змв/(1+ а)' = ! + г((1 + и/е)* " /а(1 + а) < ! + ~ ~ ~((1~ з!)(1 + ж — ( + Лв) 1и(1+ ~))) и (в+ э!2вв)!п(1+ о) > во+ 1 — а/3. Таким образом, 1 < г(г(, вз! )и з!) = ев(вз1)пз!) Г2 1 / / 2 ( )) -г г в )аз! 2.1 ((, )/0 если в/(1об з!) г -+ оо, Сходимость этого асимптотяческого вмражения довольно слабая (см.
таба. 2). 31. Когда !в = О, маркируется первый блок и затем периодически маркируется следую. щий блок, который разделяет диск с одним нз тех блоков, которые находятся в группе, начинающейся с ранее маркированного блока. Например, если хронологический порядок обращения к диску — 112020121210122, маркировка будет иметь вид П2020121в1012Й.
Таким образом, прн Р -+ оо считывается в среднем Я(12)п блоков в течение и тактов времени, где Я вЂ” функция Раманьяиа, определенная в соотношении 1.2,11.3-(2). И напротив, г(з), 2) = (з! + 1)/2 дает значительно более пессимистяческую оценку. РАЗДЕЛ б.б 1. Трудно решить, какой алгоритм сортировки наилучший в двиной ситувднн. 3 2. Прн малых Х наилучшим будет метод вставки в список; при средних значениях !гг, например при Ж = 64, — метод «лняния списков; Фри больших зэ." — метод поразрядной сортировки списка. 3. (Решение В.
Пратта (У. Ргащ).) Пусть задавив две неубывающие серии а и б и вх нужно слить. Определим очевндвым способом полсерии агагаг!уз!)г!уг, такие, что пг я,дг содержат в точности ключи из а и !), имеющие медванное значение всего массива. Выполнив "перебрасывание" подсерий, сформируем сначала азаг)уз" овяА!уг, вате~в аздзаг;3г агав и, наконец, — азбгаг))гав!)г В результате можно свести задачу к слиянию я я подмассивов ого н агав, имеющих длину < Х/2. Значительно более сложный аягорнтм предложен Л, Трабб Пардо (Ь. ТгаЬЬ Ратно). Этот алгоритм обеспечивает наилучший кз возыожных резульшт в асимптотическом смыщзе.
Можно выполнять устойчивое слияние за время порядка 0(зч) и сортировать за время порядка С()Т1оК )Т), используя только 0(1оК )Т) бит дополнительной памяти для фиксированного чадила индексных переменных, причем ие требуется никакого специального преобразования исходных данных ]ем. $!СОМР 6 (1977), 361-372]. Те же самые показатели по времени выполнения и объему памяти получены в работе В.-С.
Нпавб, М. А. 1 авудзоп, Сошр. У. Зб (1992), 643-650. См. также А. Еуштоиы, Сошр. Х 38 (1993), 681-690, где описан метод устойчивого слияния М авементов в )Т, если М значительно меньше, чем )Р. 4. Только методы простой вставки, вставки в список и слияния списков. Некоторые варианты метода быстрой сортировки также можно сделать бережливыми, ио только ценой дополнительных операций во внутреннем цикле (см. упр. 5.2.2-24).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
