Глава 7. Сводимость

алгоритм Штрассена умножения матриц, модифицированный для бу­лева случая (пример 27.2), имеет сложность O(n^1о&⁷). Но для неболь­ших значений n условия 1—3 здесь выполняться не будут. Однако со­отношение (28.6) можно доказать при более слабых предположени­ях, чем использованные выше, и обсуждавшееся доказательство не по­требует больших изменений. А именно, достаточно предположить, что B{n) удовлетворяет условиям 2—3 для n > n₀, где n₀ — некоторое на­туральное число (см. задачу 143б). Получится оценка T{n) s= cB{n), где c зависит от B(n₀), но эта зависимость не влияет на (28.6).

Для нахождения транзитивно-рефлексивного замыкания ориенти­рованного графа с n вершинами существует алгоритм, сложность ко­торого допускает оценку O(n²>⁸²), или, более точно, оценку O(n^1о&7).

Как показывает последний пример, если P ^ Q, то прогресс в уме­нии быстро решать задачу Q может в некоторых случаях обеспечить прогресс и в умении быстро решать задачу P. Но это не всегда так. Допустим, что n является нижней границей сложности для алгорит­мов решения задачи Q и в то же время для задачи P имеется алго­ритм решения со сложностью, меньшей n. Согласно определению 28.1 мы имеем P ^ Q, но наличие этой линейной сводимости ничего не дает для продвижения в умении быстро решать задачу P.

Отношение линейной сводимости, очевидно, рефлексивно. Если не рассматривать упомянутых в определении 28.1 дополнительных условий, то это отношение будет транзитивным. В тех случаях, когда такие условия наложены, необходима осмотрительность: если для за­дач P, Q и R мы имеем P ^ Q при некоторых условиях на сложность алгоритмов решения Q, а также Q ^ R при соответствующих условиях на сложность алгоритмов решения R, то чтобы на основании этого утверждать, что P ^R, надо дополнительно установить, что сложно­сти тех алгоритмов решения задачи Q, которые сопоставляются алго­ритмам решения задачи R, удовлетворяют условиям, налагаемым на сложности алгоритмов решения задачи Q при доказательстве отноше­ния P^Q. Это обстоятельство иногда безосновательно игнорируется.

§ 29. Линейная сводимость и нижние границы сложности

Нижеприведенная теорема является следствием определения 28.1.

Теорема 29.1. Пусть задачи P и Q таковы, что P s= Q. Пусть f(n) — асимптотическая нижняя граница сложности алгоритмов ре­шения задачи P, и при этом соотношение P^Qустанавливается без

§ 29. Линейная сводимость и нижние границы сложности 191

наложения ограничений на сложность алгоритмов решения задачи Q. Тогда f(n) является асимптотической нижней границей сложности алгоритмов решения задачи Q.

Доказательство. Для каждого алгоритма A_Q решения задачи Q найдется такой алгоритм A_P решения задачи P, для которого T_A (n) = = O(T_AQ (n)), или, эквивалентно, T_AQ (n) = П(T_AP (n)). Но T_AP (n) = = П(f(n)), следовательно, T_AQ (n) = П(/(n)). П

Если при соблюдении условия этого предложения для какого-то алгоритма A_Q решения задачи Q имеет место оценка T_A (n) = = O(f(n)), то этот алгоритм будет оптимальным по порядку слож­ности и T_A ( n) = в( f (n)). (При наличии ограничений на сложность

q

алгоритма A_Q, когда фактически предполагается, что A_Q принадле­жит некоторому классу J2, речь должна бы идти об оптимальности по порядку сложности в классе 21; но если ограничения таковы, что в класс £2. попадают наиболее рациональные алгоритмы, то упоми­нание класса Ш не обязательно.)

Пример 29.1. Вновь рассмотрим задачу построения выпуклой обо­лочки конечного множества точек с помощью арифметических опера­ций и сравнений. Многоугольник, являющийся выпуклой оболочкой, представляется массивом своих вершин в порядке их следования при обходе в некотором направлении, обычно против часовой стрелки, начиная с некоторой вершины. Мы покажем, что задача сортировки массивов вещественных чисел с помощью арифметических операций и сравнений линейно сводится к задаче построения выпуклой обо­лочки в этой постановке, считая, что в этих задачах затраты изме­ряются общим числом арифметических операций и сравнений. Но если порядок вершин выпуклой оболочки, которую надо построить, может быть произвольным, то задача меняется, и про нее мы ничего не утверждаем.

Пусть x₁,x₂,...,x_n — данный массив попарно различных веще­ственных чисел. Решив задачу построения выпуклой оболочки мно­жества точек с координатами

( x ₁,x²₁),( x₂,x ₂²),...,( x_n,x_n²)

(см. рис. 23), мы можем, двигаясь по вершинам построенного много­угольника, найти вершину с наименьшей абсциссой, а затем постро­ить массив вершин в порядке возрастания абсцисс. Сложность этой дополнительной части работы допускает оценку O(n). Легко видеть, что сложность любого алгоритма построения выпуклой оболочки не

192