§18. Нижние границы сложности рандомизированных алгоритмов 127

В дальнейшем нас не будут интересовать оптимальные стратегии, од­нако равенство

max min М{р, q) =min max M{p,q) (18.1)

p q q p

окажется для нас очень ценным.

При фиксированной стратегии р значение minM{p,q) равно ми-

q

нимальному значению среди

/_, milPi> У_.Щ2Р1> ■■■> / ,mikPi> i i i

т.е. mm^ mijPi (в качестве стратегии q, на которой достигается ми-

разом тахМ(р, о) = max У] т.-.-о,-. Это позволяет переписать равен-

Р i j ' '

нимум, выступает некоторая чистая стратегия). Аналогичным об­разом max M{p,q

р

ство (18.1) в виде

max min V т_ир₍ = min max V т^а_и (18.2)

p j 1—1 ' q i 1—1 ' '

i j

откуда следует, что для любых стратегий р = {р_ъ р₂,..., р_к) и q = (q_ls q2,---,4k) выполнено

min V т_;,р;^ max Vm;,о,. (18.3)

i j

То, что исходная матрица квадратная, не играло никакой роли в вы­воде последней формулы, каждая из переменных i и j могла пробе­гать свое множество значений. Можно даже не нумеровать строки и столбцы исходной матрицы, а дать им какие-то имена. Для мат­риц с такого рода именованием строк и столбцов чаще используют название таблица.

Вернемся теперь от матричных игр к анализу сложности алго­ритмов. Пусть имеется конечное множество .s4 алгоритмов решения некоторой задачи и конечное множество X входов фиксированного размера, и для них составлена числовая таблица, элементы которой проиндексированы элементами множества X (первый индекс) и мно­жества .s4 (второй индекс). В качестве элемента таблицы с индекса­ми х,А берется величина затрат (например, временных) С_А(х). Если рассмотреть какие-либо распределения вероятностей на X и .s4, то в силу (18.3) будем иметь

min Е_хС_А(х) s= max Е^С_А(х), (18.4)

А хХ

128 Глава 4. Нижняя граница сложности. Оптимальные алгоритмы

где символами Е_X и Е^ обозначены математические ожидания, свя­занные с заданными (произвольными) распределениями вероятно­стей на X и .s4.

Будем рассматривать рандомизированный алгоритм как конечное множество детерминированных («обычных») алгоритмов с некото­рым распределением вероятностей на нем, — о возможности такого взгляда на рандомизированные алгоритмы говорилось в конце § 8. Тогда можно определить усредненные затраты этого рандомизиро­ванного алгоритма для каждого входа. Фиксируя размер входа, мы можем рассмотреть сложность в худшем случае такого рандомизи­рованного алгоритма .s4 как максимум усредненных затрат по вхо­дам данного размера, эта сложность записана в правой части нера­венства (18.4). Левая же часть этого неравенства может быть интер­претирована как наименьшая из сложностей в среднем алгоритмов класса .s4, для определения этой сложности используется некоторое распределение вероятностей на X.

Мы приходим к принципу, предложенному А. Яо.

Теорема 18.1 (принцип Яо). Пусть для размера входа зафиксиро­вано некоторое значение n, и пусть все входы размера n образуют конечное множество X, на котором задано некоторое распределение вероятностей. Пусть ,s4 — конечное множество алгоритмов, приме­нимых к элементам множества X, и пусть на ,s4 тоже задано неко­торое распределение вероятностей. Множество .s4 с этим распреде­лением можно рассматривать как единый рандомизированный алго­ритм, считая его сложностью T(n) усредненные затраты в худшем случае. Тогда, если найти некоторую нижнюю границу f(n) сложно­стей в среднем (в соответствии с данным распределением вероят­ностей на множестве X входов размера n) всех детерминированных алгоритмов класса ,s4, то, независимо от конкретного вида распре­делений на X и .s4, будет выполняться неравенство f(n) s= T{n).

Пример 18.1. Рассмотрим произвольную рандомизированную сор­тировку массивов фиксированной длины n, которую, по крайней ме­ре теоретически, можно задать как конечное множество детермини­рованных алгоритмов сортировки массивов длины n с приписанны­ми этим детерминированным алгоритмам вероятностями, в сумме дающими единицу. (Предполагаем, что это вероятностное простран­ство алгоритмов не зависит от конкретного входа, т. е. конкретно­го массива длины n.) Тогда в соответствии с принципом Яо слож­ность этой рандомизированной сортировки не может быть меньше чем log₂n!, так как при равномерном распределении вероятностей

Задачи

129

на П_n для сложности в среднем детерминированных алгоритмов сор­тировки мы имеем в силу предложения 17.1 нижнюю границу log₂ n\ при любом n.^г

Задачи

74. Для обсуждавшихся в задаче 8 алгоритмов сортировки ваго­нов функция Зn - 1 является нижней границей их сложности, откуда следует, что тот алгоритм, который требуется указать в задаче 8, яв­ляется оптимальным в рассматриваемом классе.

74. Для сложности класса обсуждавшихся в задаче 17 алгоритмов поиска двери в стене функция n является асимптотической нижней границей, откуда следует, что тот алгоритм, который требуется ука­зать в задаче 17, является оптимальным по порядку сложности в рас­сматриваемом классе.

76. (Продолжение предыдущей задачи.) Для поиска двери мож­ но указать класс .s4 алгоритмов, каждый из которых определяется некоторым целым k ^ 2: путник делает k шагов вправо, и если дверь не найдена, то возвращается назад и делает k шагов влево, и опять возвращается назад, если дверь не найдена; затем делает k² шагов вправо, возвращаясь назад в случае неуспеха, затем k² шагов вле­ во и т.д. Таким образом, ^ = {A₂,A_Ъ, ...}, и для сложности по числу шагов имеем T_A (n) = Зn, если k = n, и T_A (n) > Зn, если k ф n. Как следствие, в классе j4 нет оптимального алгоритма, но каждый алго­ ритм из этого класса является оптимальным в нем по порядку слож­ ности.

Указание. Пусть m таково, что k^m-¹ <nЦk^m. Возможно, что потребуется число шагов, равное 2(k + k² +... + k^m) + 2(k + k² + ... + k^m-1) + n.

77. Нарисовать дерево быстрой сортировки для случая n = 3, счи­ тая, что первый элемент всегда выбирается в качестве разбивающего.

78. Дать другое доказательство предложения 14.2. Рассмотреть последовательности из нулей и единиц, соответствующие результа­ там всех проводимых сравнений в процессе применения сортировки к массивам длины n (каждому массиву сопоставляется своя последо­ вательность).

Указание. Если некоторый алгоритм сортировки требует не более h(n) сравнений, то длина каждой из последовательностей не превосходит h(n), и общее число последовательностей не превосходит 2^{h n}.

Дополнительные примеры применения принципа Яо можно найти в [55, гл. 2].

130 Глава 4. Нижняя граница сложности. Оптимальные алгоритмы

79. Аналогично предыдущей задаче, дать другое доказательство предложения 14.4.

79. Как уже отмечалось (со ссылкой на приложение D), n является нижней границей сложности как по числу аддитивных операций, так и по числу умножений для класса алгоритмов, вычисляющих значе­ние полинома a_nxⁿ + ... + a_гx + a₀ с помощью операций сложения, вы­читания и умножения (при рассмотрении числа n как размера входа x, a₀, a_ъ ..., a_n). Означает ли это, что при вычислении любого фикси­рованного полинома p(x) степени n при заданном значении перемен­ной x потребуется не менее n аддитивных операций и n умножений? Указать такие нижние границы сложности (по числу аддитивных опе­раций и по числу операций умножения) алгоритмов вычисления по­линома 2 ( n )x^k, которые растут при n —»оо существенно медленнее,

^k=0

чем n.

81. Имеется плитка шоколада размера k х l клеток, которую тре­буется разломать на отдельные клетки. Каждый разлом применяет­ся к одному куску плитки и производится по прямой линии. Затра­ты каждого алгоритма решения этой задачи применительно к кон­кретной плитке измеряются числом потребовавшихся разломов. Ука­зать оптимальный алгоритм решения этой задачи и выписать его сложность. Числа k, l считаются параметрами размера входа алго­ритмов.

81. Если условно изобразить элементы массива длины n точками на плоскости, соединяя отрезками те из них, которые непосредствен­но сравнивались в процессе некоторого алгоритма поиска, — скажем, поиска наименьшего элемента, одновременного поиска наибольшего и наименьшего элементов, поиска k-го по величине элемента (в част­ности, поиска медианы, т.е. |"§]-го элемента), —то получающийся граф должен быть связным, иначе мы бы ничего не могли сказать о том, как соотносятся между собой элементы из разных компонент. Показать, что для всех алгоритмов поиска, сопоставляющих указан­ным (неявным) образом связные графы конкретным массивам, n - 1 является нижней границей сложности по числу сравнений (как в худ­шем случае, так и в среднем); в частности, это верно для алгоритмов поиска медианы.

Указание. Дерево с n вершинами имеет n - 1 ребро.

83. Рассмотрим класс алгоритмов поиска k первых (меньших) по величине элементов массива без установления порядка между най­ денными элементами и класс алгоритмов поиска k-го по величине

Задачи

131

элемента. Как обычно, имеется в виду поиск с помощью сравнений. Доказать, что любая нижняя граница сложности по числу сравнений алгоритмов первого класса является нижней границей и для второго класса.

84. Дать доказательство предложения 14.1, построенное по той же схеме, что и доказательство предложения 15.1.

Указание. Рассмотреть тройки множеств (A, B, C), включая в A на каждом этапе алгоритма все те элементы, которые еще не сравнивались, в B — все те, которые участвовали в сравнениях и всегда оказывались меньшими, в C — все те, которые участвовали в сравнениях и в некоторых оказывались большими.

85. Доказать содержащееся в доказательстве предложения 15.1 ут­верждение, что после первого сравнения постоянно будет выполнено b^l, c^1.

85. В классе алгоритмов вычисления aⁿ с помощью умножений (a фиксировано, n е N) при рассмотрении n в качестве размера входа существует оптимальный алгоритм. То же самое—при рассмотрении m = A(n) в качестве размера входа.

85. Бинарный алгоритм возведения в степень n не является опти­мальным по числу умножений и при использовании m = А(n) в каче­стве размера входа.

Указание. Рассмотреть алгоритм, который для всех n ф 15 работает как бинарный алгоритм, а при n = 15 — несколько быстрее (см. задачу 19), и по­казать, что такой алгоритм при m = 4 имеет сложность меньшую, чем би­нарный.

88. (Продолжение задачи 87.) Является ли оптимальным по по­рядку сложности бинарный алгоритм возведения в степень n при ис­пользовании m = A(n) в качестве размера входа?

88. Рассмотренный в задаче 64 алгоритм поиска фальшивой мо­неты, требующий в худшем случае не более [log₃ n] взвешиваний, является оптимальным для худшего случая.

88. Нижней границей сложности любого алгоритма деления от­резка на n равных частей с помощью циркуля и линейки (см. зада­чу 18) при рассмотрении числа n в качестве размера входа является,

n-1 в частности, —^—.

91. Отсутствие указания основания логарифма в (16.1) является корректным.

91. Функция log₂(n + l) является нижней границей сложности в среднем алгоритмов поиска места элемента в упорядоченном массиве

91. 132 Глава 4. Нижняя граница сложности. Оптимальные алгоритмы

длины п с помощью сравнений (считаем, что в диапазоне от 1 до п + 1 место может быть любым с одинаковой вероятностью ₊-).

Указание. Для доказательства воспользоваться предложением 17.1.

93. (Продолжение предыдущей задачи.) Алгоритм бинарного по­иска является оптимальным в среднем по порядку сложности в классе алгоритмов поиска места элемента с помощью сравнений.

93. Алгоритм, описанный в задаче 29, является оптимальным как в худшем случае, так и в среднем.

93. Пусть T_QS(n) и 7^p_t(n) — сложности в среднем быстрой сорти­ровки и оптимальной в среднем сортировки. Верно ли, что Гд₅(п)~ ~T_opt(n)? Если нет, то можно ли подобрать константу с такую, что f_Q(n)~cf_opt(n)?

93. Утверждение теоремы 17.1 перестает быть верным, если его изменить, удалив условие, что т < °° всюду на рассматриваемом ве­роятностном пространстве: при выполнении всех остальных условий

со

может оказаться, что т = °° при том, что X! ^fc имеет конечное зна-

fc=i чение.

Указание. Рассмотреть постоянные величины g_fc = ^г к = 1,2,...,

взяв h_k = Е,_к для всех к; при любом q > 1 получается противоречие с изме­ненным утверждением.^г

97. Функция log₂(n + 1) является нижней границей сложности ран­ домизированных алгоритмов поиска места элемента в упорядочен­ ном массиве длины п с помощью сравнений. (Предполагается, что каждый из рассматриваемых рандомизированных алгоритмов может быть задан как конечное множество детерминированных алгоритмов поиска места элемента в упорядоченном массиве длины п, с при­ писанными этим детерминированным алгоритмам вероятностями, в сумме дающими единицу; при этом такое вероятностное простран­ ство алгоритмов не должно зависеть от конкретного входа разме­ ра п.)

Эта задача сообщена автору А.В.Бернштейном.