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

сектора пространства Ж". В примере 14.2 говорилось, что при фикси­рованном п любую сортировку массивов длины п можно представить в виде дерева, каждой не являющейся листом вершине v которого приписано сравнение вида x_t < х_;-, а выходящие из нее ребра име­ют метки 1 («да») и 0 («нет»); при этом каждому листу Z приписан набор х; ,х< ,...,х; , где (b,i₂, ...,*„) — некоторая перестановка чисел 1,2,...,п.

Алгоритм сортировки массивов длины п c помощью сравнений и четырех арифметических операций представляется деревом D, которое можно считать таким, что каждой не являющейся ли­стом вершине v приписано сравнение F_v(x₁,x₂,...,x_n) с нулем, где Р_у(х_ъх₂,...,х_п) — некоторая рациональная функция, а выходящие из вершины ребра имеют метки 1 («да») и 0 («нет»). При этом каждому листу Z приписаны рациональные функции

G_ll{x₁,x₂,...,x_n), G_l2{x₁,x₂,...,x_n), ..., G_ln(x₁,x₂,...,x_n), (29.2)

значения которых для исходных х_ъх₂, ...,х_п определяют требуемый

порядок X; , X; , ...,Х; :

х =G,₁(x₁,x₂,...,x_n), х =G,₂(x₁,x₂,...,x_n),

- =G,_n(x₁,x₂,...,x_n).

Можно считать, что числитель каждой из функций F_v(x_l5x₂, ...,х_п) не является нулевым полиномом, — в противном случае вершину v можно было бы удалить из дерева вместе с выходящей из нее вет­вью, начинающейся с помеченного единицей ребра. Множество JV тех точек Ж", в которых обращается в нуль числитель хотя бы одной из рациональных функций F_v(x_l5x₂, ...,х_п), в силу свойства (R1) явля­ется замкнутым, причем это множество не может покрывать целиком ни один из секторов. Иначе в силу свойства (R2) произведение всех числителей рассматриваемых рациональных функций было бы нуле­вым полиномом, а это означало бы, что один из сомножителей этого произведения—нулевой полином.

Таким образом, каждое из множеств

S; = S;\JV, i = l,2,...,n!,

есть непустое открытое множество. Покажем, что для массивов, соот­ветствующих точкам из S'_t, i = l,2,..., п\, рассматриваемая сортировка в худшем случае требует не менее [log₂n!l сравнений.

§ 30. Классы PиNp

195

Будем говорить, что точка (x_ъx₂, ...,x_n) некоторого сектора со­гласуется с листом l дерева D, если соответствующая дереву D сор­тировка массива x_ъx₂, ...,x_n заканчивается в листе l.

В том случае, когда D имеет не менее n\ листьев, мы, рассуждая так же, как в примере 14.2, получаем, что высота дерева D (слож­ность сортировки по числу сравнений) не может быть меньше чем [log₂ n\]. Допустим, что число листьев дерева D меньше чем n\. Тогда найдется лист l такой, что имеются точки в двух разных множествах S[, S'j, согласующиеся с l. В силу свойства (R1) найдутся непустые открытые множества U_г с S[, U₂ с S' такие, что любая точка, принад­лежащая какому-то одному из них, согласуется с листом l. Если ли­сту l приписан массив (29.2), то для некоторых целых k,s, t, не мень­ших единицы и не превосходящих n, таких, что s^t, будем иметь G_k(x₁,x₂,...,x_n) = x_s при (x₁,x₂,...,x_n)&U₁ и G_k(x₁,x₂,...,x_n)=x_t при {x_ъx₂,...,x_n)&U₂. Но значения рациональной функции на одном из множеств U_ъ U₂ однозначно определяют значения этой рациональ­ной функции всюду на U_г и U₂ (это выводится из свойства (R2)), поэтому из того, что, например, G_k(x_ls x₂, ...,x_n) = x_s на U_ъ следует, что G_k(x_l5x₂, ...,x_n) = x_s на U₂. Но мы знаем, что G_k(x_l5x₂, ...,x_n) =x_t на U₂. Так как s/t, то в любом секторе x_sфx_t, в частности, это так и в секторе, подмножеством которого является U₂. Противоречие. □

Из доказанного предложения следует, что f(n) = nlogn является асимптотической нижней границей сложности алгоритмов сортиров­ки массивов длины n попарно различных вещественных чисел c по­мощью сравнений и четырех арифметических операций. По теоре­ме 29.1 эта функция является также асимптотической нижней оцен­кой для алгоритмов построения выпуклой оболочки.

Любой алгоритм построения выпуклой оболочки с помощью арифметических операций и сравнений, который имеет сложность O(nlogn), является оптимальным по порядку сложности по общему числу операций, и его сложность есть G(nlogn). Алгоритм Грэхема построения выпуклой оболочки (пример 3.1) является оптималь­ным по порядку сложности по общему числу операций, коль скоро используемая им сортировка имеет сложность O(nlogn) по числу сравнений.