диске j будут считаны во время <t + Nj; все они должны принять участие в слиянии во время t + тах(Ло,..., Nd-i).

(b) Если ((5 + 1)-й блок после маркированного блока не удален, то можно использовать тот же аргумент. В проишном случае предыдущие Q не маркированы и Q + 2 блоков не могут размещаться на разных дисках.

(c) Разделите хронологический порядок блоков на группы размером Q + 2 и рассмотрите любую из них. Если существует Mk блоков из серии к, то числа Nj эквивалентны числу щаров в j-й урне в задаче о циклической занятости при n = Dnm = Q + 2. Таким образом, ожидаемое число маркированных ячеек не превышает верхней оценки в упр. 27, (Ь). Обозначим эту верхнюю оценку через Cnim). Тогда r{d,m) = {d/m)ed{Tn).

[В действительности такая функция г(2, тп) не монотонна по тп, когда тп мало. Таким образом, элементы, перечисленные в табл. 2 для г(2,4) и г(2,12), в действительности являются значениями г(2,3) и г(2,11). Дополнительные буфера не могут увеличить число маркированных блоков.]

30. Пусть l=\(s + V2s) Ind], а = у/2/s. Тогда

eaisdlnd) < I + d(l + a/d)"""7(l + a)

= / + d(l + a/d)"""7a(l + a) <l + a~ exp((lnd)(l + sa - {s + VTs) ln(l -I- a))) и {s + y/Ts) ln(l + a) > sa + 1 - a/3. Таким образом,

<-.«"») = < + У!+ TSES ( + b.. o(,-.Cog.,,),

если s/(logd) -> 00. Сходимость этого асимптотического выражения довольно слабая (см. табл. 2).

31. Когда (5 = 0, маркируется первый блок и затем периодически маркируется следующий блок, который разделяет диск с одним из тех блоков, которые находятся в группе, начинающейся с ранее маркированного блока. Например, если хронологический порядок обращения к диску - 112020121210122, маркировка будет иметь вид П2020121210122. Таким образом, при Р -> оо считывается в среднем Q{D)n блоков в течение п тактов времени, где Q - функция Раманьяна, определенная в соотношении 1.2.11.3-(2). И напротив, r{d, 2) = {d+ 1)/2 дает значительно более пессимистическую оценку.

РАЗДЕЛ 5.5

1. Трудно решить, какой алгоритм сортировки наилучший в данной ситуации.

2. При малых Л наилучшим будет метод вставки в список; при средних значениях N, например при Л = 64, - метод слияния списков; при больших Л - метод поразрядной сортировки списка.

3. (Решение В. Пратта (V. Pratt).) Пусть заданы две неубывающие серии а и /3 и их нужно слить. Определим очевидным способом подсерии aiaiasifiifis, такие, что аг и /Зг содержат в точности ключи из а и /3, имеющие медианное значение всего массива. Выполнив "перебрасывание" подсерий, сформируем сначала aia2/3f af/Зг/Зз, затем - ai/Sial/Sf аз/Зз и, наконец, - а1/31а2/3газ/3з. В результате можно свести задачу к слиянию подмассивов ai/3i и аз/Зз, имеющих длину < N/2.

Значительно более сложный алгоритм предложен Л. Трабб Пардо (L. Trabb Pardo). Этот алгоритм обеспечивает наилучший из возможных результат в асимптотическом смысле. Можно выполнять устойчивое слияние за время порядка 0(N) и сортировать за

время порядка 0{Nlog N), используя только 0(logA) бит дополнительной памяти для фиксированного Hiiuia индексных переменных, причем не требуется никакого специального преобразования исходных данных [см. SICOMP 6 (1977), 351-372]. Те же самые показатели по времени выполнения и объему памяти получены в работе В.-С. Huang, М. А. Langston, Сотр. J. 35 (1992), 643-650. См. также А. Symvonis, Сотр. J. 38 (1995), 681-690, где описан метод устойчивого слияния М элементов в N, если М значительно меньше, чем N.

4. Только методы простой вставки, вставки в список и слияния списков. Некоторые варианты метода быстрой сортировки также можно сделать бережливыми, но только ценой дополнительных операций во внутреннем цикле (см. упр. 5.2.2-24).

Особое значение приобретают бережливые методы в том случае, когда результат сравнения обладает надежностью на все 100% (см. D. Е. Knuth, Lecture Notes in Сотр. Sci. 606 (1992), 61-67).

РАЗДЕЛ 6.1

1. V{N - 1)/12; CM. уравнение 1.2.10-(22).

2. Si. [Инициализация.] Установить P <- FIRST.

S2. [Сравнение.] Если К = KEY(P), алгоритм успешно завершается. S3. [Продвижение.] Установить Р Ч- LINK(P).

S4. [Конец файла?] Если Р # Л, перейти к шагу S2. В противном случае алгоритм завершается неудачно.

Бремя выполнения равно (6С - 3S + 4)u.

4. Да, если можно установить KEY (Л) равным К. (Впрочем, метод дублирования цикла из программы Q в этом случае не даст никаких преимуществ.)

5. Нет, программа Q всегда выполняет не меньше операций, чем программа Q.

6. Замените команды строки 08 командами JE *+4; СМРА KEY+N+2,1; JNE SB; INCl 1, a команды строк 03 и 04 - командами ENTl -2-N; ЗН INCl 3.

7. Заметьте, что Cn = jCyv-i + 1.

8. Формула суммирования Эйлера дает

(Из теории функций комплексных переменных известно, что

С(х) = 2V- sin(i7rx)r(l - х)С(1 - х). Эта формула наиболее полезна при х < 0.)

9. (а) Да: Cn=N- NHJTl = iV + 1 - n" Н = jn + i + 0{n-).

(b) Cn = j{i + n/{i- (V))) = + л-7г(1 - ) + 1) + 0{n-).

(c) При в < 0 (11) не является распределением вероятностей; (16) дает оценку Cn =

10. Pl < < pn; (максимальное Cn) = {n + 1) - (минимальное Cn)- (Аналогично в записях с переменной длиной максимальное среднее время поиска равно Li{l + pi) + - - - + Ln{1 +Pn) минус минимальное среднее время поиска.)

11. (а) Произведения fm-iixi,... ,Xi i)pi представляют собой вероятности возможных последовательных запросов, после выполнения которых элемент Ri оказывается на т-м месте. (Ь) Второе тождество получается после суммирования всех () вариантов первого подмножества на различных т-подмножеств ах X с учетом того, что каждый из них встречается Рпк раз. Третье тождество является результатом обращения второго. (Можно также использовать принцип включения и исключения.) (с) Ет>0~ nQnn - Qn{n-l),

а потому

d. = i+(iv-i)-..e,Tb;

i tpi+PJ Pi+Pjj

Примечание. В. Дж. Хендрикс (W. J. Hendricks) [J. Applied Probability 9 (1972), 231-233] нашел простую формулу для финальных вероятностей каждой перестановки записей. Например, при n = 4 предельная вероятность последовательности Кз Ri R4 R2 равна

рз Pl Pi Р2

РЗ+Р1+Р4+Р2 Р1+Р4+Р2 Р4+Р2 Р2

Джеймс Битнер (James Bitner) [SICOMP 8 (1979), 82-85] доказал, что, если изначально список неупорядочен, ожидаемое время поиска после t случайных запросов превысит Cn на величину J2i j (Pi ~Pj )(1 ~Pi ~Pj Y/iPi +Pj)- Таким образом, для t поисков потребуется в среднем менее tCjv -(- \ij{pi - Pj)/{Pi + Pj) < Cn + \ {1) сравнений. См. также доказательство с применением производящих функций в работе Р. Flajolet, D. Gardy, and L. Thimonier, Discrete Applied Math. 39 (1992), 207-229, §6.

12. Cn = 2- + 2j2n=o V(2" + !)• Это выражение быстро сходится к 2а « 2.5290; в упр. 5.2.4-13 дано значение а с точностью до 40 знаков.

13. После выполнения весьма утомительного суммирования

А 2„ n(n + l)(2n+l),, n(n+l)(10n-l)

> fc Мп+к = -5-(2Л2п - Нп)-----

получим ответ:

Cn = \N- (2iV + 1)(Я2„ - Я„) + I - \{N + \)- а .409iV.

14. В предположении, что xi < Х2 < < Хп, максимальное значение достигается при 2/ai < Уа2 < • • • < 2/а„ И минимальное - при 2/ai > • • > 2/а„. Рассуждения аналогичны рассуждениям при доказательстве теоремы S.

15. Рассуждая так же, как в теореме S, можно прийти к выводу, что расположение R1R2 ... Rn оптимально тогда и только тогда, когда

Pi/Li(l -Pi)> > Pn/Ln{1 - Pn).