Лекции о сложности алгоритмов. С. А. Абрамов (1121249), страница 39

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 39)

В тех случаях, когдатакие условия наложены, необходима осмотрительность: если для задач P, Q и R мы имеем P ¶ Q при некоторых условиях на сложностьалгоритмов решения Q, а также Q ¶ R при соответствующих условияхна сложность алгоритмов решения R, то чтобы на основании этогоутверждать, что P ¶ R, надо дополнительно установить, что сложности тех алгоритмов решения задачи Q, которые сопоставляются алгоритмам решения задачи R, удовлетворяют условиям, налагаемым насложности алгоритмов решения задачи Q при доказательстве отношения P ¶ Q. Это обстоятельство иногда безосновательно игнорируется.§ .

Линейная сводимость и нижние границы сложностиНижеприведенная теорема является следствием определения ..Теорема .. Пусть задачи P и Q таковы, что P ¶ Q. Пустьf (n) — асимптотическая нижняя граница сложности алгоритмов решения задачи P, и при этом соотношение P ¶ Q устанавливается без§ . Линейная сводимость и нижние границы сложностиналожения ограничений на сложность алгоритмов решения задачи Q.Тогда f (n) является асимптотической нижней границей сложностиалгоритмов решения задачи Q.Доказательство. Для каждого алгоритма AQ решения задачи Qнайдется такой алгоритм A P решения задачи P, для которого TAP (n) == O(TAQ (n)), или, эквивалентно, TAQ (n) = Ω(TAP (n)).

Но TAP (n) == Ω( f (n)), следовательно, TAQ (n) = Ω( f (n)).Если при соблюдении условия этого предложения для какого-тоалгоритма AQ решения задачи Q имеет место оценка TAQ (n) == O( f (n)), то этот алгоритм будет оптимальным по порядку сложности и TAQ (n) = Θ( f (n)). (При наличии ограничений на сложностьалгоритма AQ , когда фактически предполагается, что AQ принадлежит некоторому классу Q , речь должна бы идти об оптимальностипо порядку сложности в классе Q ; но если ограничения таковы, чтов класс Q попадают наиболее рациональные алгоритмы, то упоминание класса Q не обязательно.)Пример .. Вновь рассмотрим задачу построения выпуклой оболочки конечного множества точек с помощью арифметических операций и сравнений.

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

Решив задачу построения выпуклой оболочки множества точек с координатами(x1 , x12 ), (x2 , x22 ), ..., (xn , xn2 )(см. рис. ), мы можем, двигаясь по вершинам построенного многоугольника, найти вершину с наименьшей абсциссой, а затем построить массив вершин в порядке возрастания абсцисс. Сложность этойдополнительной части работы допускает оценку O(n). Легко видеть,что сложность любого алгоритма построения выпуклой оболочки неГлава . Сводимостьyy = x2......xРис. .

Сведение сортировки чисел x1 , x2 , ..., xn , отмеченных на оси абсцисс,к построению выпуклой оболочки точек (x1 , x12 ), (x2 , x22 ), ..., (xn , xn2 ).может быть меньше чем n. Таким образом, каждому алгоритму Aпостроения выпуклой оболочки мы сопоставляем алгоритм сортировки со сложностью O(TA (n)). Следовательно, задача сортировки вещественных чисел с помощью арифметических операций и сравненийлинейно сводится к задаче построения выпуклой оболочки.Из результатов §  следует, что любая сортировка с помощьюсравнений массивов длины n имеет сложность не менее log2 n!. Нопри построении выпуклой оболочки используются как сравнения, таки арифметические операции. Можно ли, привлекая помимо операций сравнения еще и арифметические операции, предложить алгоритм сортировки массивов вещественных чисел, сложность которогопо числу сравнений была бы меньше, чем log2 n!, пусть даже при том,что потребовалось бы очень большое число арифметических операций? Ниже мы обосновываем отрицательный ответ на этот вопрос.Дополнительное использование четырех арифметических операций означает, что сравниваться могут не только числа x1 , x2 , ..., xn ,заданные изначально, но и значения рациональных функций от этихчисел.

В качестве знаков сравнения могут использоваться<, >, =, 6=, ¶, ¾ .Каждая рациональная функция F(x1 , x2 , ..., xn ) записывается какотношение двух полиномовF(x1 , x2 , ..., xn ) =p(x1 , x2 , ..., xn )q(x1 , x2 , ..., xn )(.)§ . Линейная сводимость и нижние границы сложности(в этом параграфе мы рассматриваем рациональные функции иполиномы с вещественными коэффициентами). Каждый полиномf (x1 , x2 , ..., xn ) можно рассматривать как рациональную функциюf (x1 , x2 , ..., xn ).1Предполагается, что если алгоритм предписывает сравнение, в котором участвует значение рациональной функции (.), то ее знаменатель q(x1 , x2 , ..., xn ) не обращается в  при рассматриваемых значениях x1 , x2 , ..., xn . Неравенство F1 (x1 , x2 , ..., xn ) < F2 (x1 , x2 , ..., xn ) равносильно, очевидно, неравенству F(x1 , x2 , ..., xn ) < 0, гдеF(x1 , x2 , ..., xn ) = F1 (x1 , x2 , ..., xn ) − F2 (x1 , x2 , ..., xn ).То же самое для сравнений со знаками >, =, 6=, ¶, ¾.Далее будут использоваться два свойства рациональных функций:(R) Множество точек (x1 , x2 , ..., xn ) ∈ Rn , для которых данная рациональная функция (.) неопределена или равна нулю, являетсязамкнутым; в свою очередь, те точки, в которых эта функция определена и имеет значение большее (меньшее) нуля, образуют открытоемножество.

Это следует из того, что рациональная функция непрерывна на своем множестве определения.(R) Если рациональная функция (.) определена и равна нулювсюду на некотором непустом открытом подмножестве множества Rn ,то ее числитель p(x1 , x2 , ..., xn ) является нулевым полиномом (см. задачу ).Предложение .. Функция f (n) = ⌈log2 n!⌉ является нижней границей сложности по числу сравнений алгоритмов сортировки массивов длины n попарно различных вещественных чисел c помощью сравнений и четырех арифметических операций.Доказательство.  Каждой из перестановок a = (a1 , a2 , ..., an ) ∈ Πnсопоставим сектор Sa — подмножество пространства Rn такое, что(x1 , x2 , ..., xn ) ∈ Sa , если и только если числа x1 , x2 , ..., xn попарно различны и их относительный порядок совпадает с относительным порядком чисел a1 , a2 , ..., an .

Любой сектор является открытым множеством в Rn . Каждому массиву вещественных чисел с попарно различными элементами x1 , x2 , ..., xn соответствует точка некоторогоИдея элементарного доказательства сообщена автору С. П. Поляковым. Наиболеераннее (довольно трудное для понимания) доказательство было опубликовано H.

Фридманом в [].Глава . Сводимостьсектора пространства Rn . В примере . говорилось, что при фиксированном n любую сортировку массивов длины n можно представитьв виде дерева, каждой не являющейся листом вершине v которогоприписано сравнение вида xi < x j , а выходящие из нее ребра имеют метки 1 («да») и 0 («нет»); при этом каждому листу l приписаннабор xi1 , xi2 , ..., xin , где (i1 , i2 , ..., in ) — некоторая перестановка чисел1, 2, ..., n.Алгоритм сортировки массивов длины n c помощью сравненийи четырех арифметических операций представляется деревом D,которое можно считать таким, что каждой не являющейся листом вершине v приписано сравнение Fv (x1 , x2 , ..., xn ) с нулем, гдеFv (x1 , x2 , ..., xn ) — некоторая рациональная функция, а выходящие извершины ребра имеют метки 1 («да») и 0 («нет»).

При этом каждомулисту l приписаны рациональные функцииGl1 (x1 , x2 , ..., xn ),Gl2 (x1 , x2 , ..., xn ), ...,Gln (x1 , x2 , ..., xn ),(.)значения которых для исходных x1 , x2 , ..., xn определяют требуемыйпорядок xi1 , xi2 , ..., xin :xi1 = Gl1 (x1 , x2 , ..., xn ),xi2 = Gl2 (x1 , x2 , ..., xn ),.......................xin = Gln (x1 , x2 , ..., xn ).Можно считать, что числитель каждой из функций Fv (x1 , x2 , ..., xn )не является нулевым полиномом, — в противном случае вершину vможно было бы удалить из дерева вместе с выходящей из нее ветвью, начинающейся с помеченного единицей ребра.

Характеристики

Список файлов лекций