С.А. Абрамов - Лекции о сложности алгоритмов (pdf) (1123764), страница 38

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

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

(При наличии ограничений на сложностьалгоритма 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можно было бы удалить из дерева вместе с выходящей из нее ветвью, начинающейся с помеченного единицей ребра.

Множество Nтех точек Rn , в которых обращается в нуль числитель хотя бы однойиз рациональных функций Fv (x1 , x2 , ..., xn ), в силу свойства (R) является замкнутым, причем это множество не может покрывать целикомни один из секторов. Иначе в силу свойства (R) произведение всехчислителей рассматриваемых рациональных функций было бы нулевым полиномом, а это означало бы, что один из сомножителей этогопроизведения — нулевой полином.Таким образом, каждое из множествS′i = Si \ N,i = 1, 2, ..., n!,есть непустое открытое множество. Покажем, что для массивов, соответствующих точкам из S′i , i = 1, 2, ..., n!, рассматриваемая сортировкав худшем случае требует не менее ⌈log2 n!⌉ сравнений.§ .

Классы P и NPБудем говорить, что точка (x1 , x2 , ..., xn ) некоторого сектора согласуется с листом l дерева D, если соответствующая дереву D сортировка массива x1 , x2 , ..., xn заканчивается в листе l.В том случае, когда D имеет не менее n! листьев, мы, рассуждаятак же, как в примере ., получаем, что высота дерева D (сложность сортировки по числу сравнений) не может быть меньше чем⌈log2 n!⌉. Допустим, что число листьев дерева D меньше чем n!. Тогданайдется лист l такой, что имеются точки в двух разных множествахS′i , S′j , согласующиеся с l. В силу свойства (R) найдутся непустыеоткрытые множества U1 ⊂ S′i , U2 ⊂ S′j такие, что любая точка, принадлежащая какому-то одному из них, согласуется с листом l. Если листу l приписан массив (.), то для некоторых целых k, s, t, не меньших единицы и не превосходящих n, таких, что s 6= t, будем иметьGk (x1 , x2 , ..., xn ) = x s при (x1 , x2 , ..., xn ) ∈ U1 и Gk (x1 , x2 , ..., xn ) = xt при(x1 , x2 , ..., xn ) ∈ U2 .

Но значения рациональной функции на одном измножеств U1 , U2 однозначно определяют значения этой рациональной функции всюду на U1 ∪ U2 (это выводится из свойства (R)),поэтому из того, что, например, Gk (x1 , x2 , ..., xn ) = x s на U1 , следует,что Gk (x1 , x2 , ..., xn ) = x s на U2 . Но мы знаем, что Gk (x1 , x2 , ..., xn ) = xtна U2 . Так как s 6= t, то в любом секторе x s 6= xt , в частности, это таки в секторе, подмножеством которого является U2 .

Противоречие.Из доказанного предложения следует, что f (n) = n log n являетсяасимптотической нижней границей сложности алгоритмов сортировки массивов длины n попарно различных вещественных чисел c помощью сравнений и четырех арифметических операций. По теореме . эта функция является также асимптотической нижней оценкой для алгоритмов построения выпуклой оболочки.Любой алгоритм построения выпуклой оболочки с помощьюарифметических операций и сравнений, который имеет сложностьO(n log n), является оптимальным по порядку сложности по общемучислу операций, и его сложность есть Θ(n log n). Алгоритм Грэхемапостроения выпуклой оболочки (пример .) является оптимальным по порядку сложности по общему числу операций, коль скороиспользуемая им сортировка имеет сложность O(n log n) по числусравнений.§ .

Классы P и NPЦель этого и следующих параграфов — дать общее, без многих деталей, представление о некоторых проблемах, касающихся алгоритмовГлава . Сводимостьполиномиально ограниченной сложности (см. § , определение .)или, другими словами, полиномиальных алгоритмов.Подход, согласно которому алгоритмы подразделяются на полиномиальные и все остальные, далеко не всегда является продуктивным с практической точки зрения (алгоритм со сложностью n100 , гдеn — размер входа, вряд ли найдет массовое применение), но при более широком взгляде этот подход имеет свою логику.

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

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