Битовая сложность

Со

Задачи

А хХ

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!, так как при равномерном распределении вероятностей

Задачи

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

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

75. Для сложности класса обсуждавшихся в задаче 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.

80. Как уже отмечалось (со ссылкой на приложение 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 считаются параметрами размера входа алго­ритмов.

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

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

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

Задачи

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

95. Пусть T_QS(n) и 7^p_t(n) — сложности в среднем быстрой сорти­ровки и оптимальной в среднем сортировки. Верно ли, что Гд₅(п)~ ~ T _opt(n)? Если нет, то можно ли подобрать константу с такую, что f _Q (n)~ c f_opt(n)?

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

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

fc=i чение.

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

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

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

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

Глава 5

Дата добавления: 2014-01-11