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

У >i

х

Рис. 23. Сведение сортировки чисел x_t,x₂, ■■■,х_п, отмеченных на оси абсцисс, к построению выпуклой оболочки точек (х_их*), {х₂,х\),..., {х_п,х²_п).

может быть меньше чем п. Таким образом, каждому алгоритму А построения выпуклой оболочки мы сопоставляем алгоритм сортиров­ки со сложностью 0{Т_А{п)). Следовательно, задача сортировки веще­ственных чисел с помощью арифметических операций и сравнений линейно сводится к задаче построения выпуклой оболочки.

Из результатов § 14 следует, что любая сортировка с помощью сравнений массивов длины п имеет сложность не менее log₂ п\. Но при построении выпуклой оболочки используются как сравнения, так и арифметические операции. Можно ли, привлекая помимо опера­ций сравнения еще и арифметические операции, предложить алго­ритм сортировки массивов вещественных чисел, сложность которого по числу сравнений была бы меньше, чем log₂ п\, пусть даже при том, что потребовалось бы очень большое число арифметических опера­ций? Ниже мы обосновываем отрицательный ответ на этот вопрос.

Дополнительное использование четырех арифметических опера­ций означает, что сравниваться могут не только числа х_ъх₂, ■■■,х_п, заданные изначально, но и значения рациональных функций от этих чисел. В качестве знаков сравнения могут использоваться

<, >, =, ф_у ^, ;>.

Каждая рациональная функция F{х_ъ х₂, ■ ■ ■, х_п) записывается как отношение двух полиномов

р(х₁,х₂,...,х_п)

(29.1)

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

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

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

(в этом параграфе мы рассматриваем рациональные функции и полиномы с вещественными коэффициентами). Каждый полином f ( x ₁, x₂,..., x_n) можно рассматривать как рациональную функцию

f(x₁,x₂,...,x_n) 1 .

Предполагается, что если алгоритм предписывает сравнение, в кото­ром участвует значение рациональной функции (29.1), то ее знамена­тель q(x₁,x₂, ...,x_n) не обращается в 0 при рассматриваемых значе­ниях x ₁,x₂, ...,x_n. Неравенство F₁(x₁,x₂,...,x_n)<F₂(x₁,x₂,...,x_n) рав­носильно, очевидно, неравенству F( x ₁,x₂, ...,x_n) <0, где

F(x₁,x₂,...,x_n)=F₁(x₁,x₂,...,x_n)-F₂(x₁,x₂,...,x_n).

То же самое для сравнений со знаками >, =, ф, ^, ^.

Далее будут использоваться два свойства рациональных функций:

(R1) Множество точек (x₁,x₂,...,x_n)еГ, для которых данная ра­циональная функция (29.1) неопределена или равна нулю, является замкнутым; в свою очередь, те точки, в которых эта функция опреде­лена и имеет значение большее (меньшее) нуля, образуют открытое множество. Это следует из того, что рациональная функция непре­рывна на своем множестве определения.

(R2) Если рациональная функция (29.1) определена и равна нулю всюду на некотором непустом открытом подмножестве множества Жⁿ, то ее числитель p( x ₁, x₂, ...,x_n) является нулевым полиномом (см. за­дачу 147).

Предложение 29.1. Функция f(n) = [log₂ n!] является нижней гра­ницей сложности по числу сравнений алгоритмов сортировки масси­вов длины n попарно различных вещественных чисел c помощью срав­нений и четырех арифметических операций.

Доказательство.^г Каждой из перестановок a = (a₁, a₂, ...,an)еПn сопоставим сектор S_a — подмножество пространства Жn такое, что ( x ₁,x₂, ...,x_n) eS_a, если и только если числа x ₁,x₂, ...,x_n попарно раз­личны и их относительный порядок совпадает с относительным по­рядком чисел a₁,a₂, ...,a_n. Любой сектор является открытым множе­ством в Жn. Каждому массиву вещественных чисел с попарно раз­личными элементами x ₁,x₂, ...,x_n соответствует точка некоторого

!Идея элементарного доказательства сообщена автору С.П.Поляковым. Наиболее раннее (довольно трудное для понимания) доказательство было опубликовано H. Фрид­маном в [49].

194