§ 16. Асимптотические нижние границы

117

Из этого примера видно, что само свойство оптимальности нахо­дится в зависимости от выбора размера входа^г.

В следующем примере, касающемся сортировки массивов, рас­сматривается сложность в худшем случае по числу сравнений.

Пример 16.4. Аналогично тому, как это сделано в примере 16.1, мы получаем, что любая сортировка, сложность которой допускает оценку О (log п!), является оптимальной по порядку сложности. В силу формулы Стирлинга мы имеем п log₂ п = 0(log п!), откуда следует, что любая сортировка, сложность которой по числу сравнений допускает оценку 0(n log п), является оптимальной по порядку сложности.

Сортировка бинарными вставками и сортировка фон Неймана яв­ляются оптимальными по порядку сложности по числу сравнений.

(Позднее мы установим оценку O(nlogn) и для сложности рекурсив­ной сортировки слияниями.) Эти сортировки имеют разные сложно­сти как функции от п: например, T_vN(5) = 9, Г_в(5) = 8. Но, повторим, их сложности являются величинами одного порядка при п—> <х>. Резюмируем наши наблюдения.

Предложение 16.1. Необходимым и достаточным условием опти­мальности сортировки по порядку сложности является справедли­вость оценки O(nlogn) для сложности этой сортировки. Если для некоторой сортировки справедлива оценка O(nlogn), то справедлива и оценка G(nlogn).

Доказательство. Достаточность уже установлена выше. Оставша­ яся часть доказательства следует, например, из теоремы 16.1 и оп­ тимальности по порядку сложности сортировки бинарными встав­ ками. □

Заметим при этом, что для сортировок бинарными вставками и фон Неймана справедливо значительно более сильное утверждение, чем утверждение об их оптимальности по порядку сложности. Для их сложностей и сложности T_opt(n) оптимального алгоритма имеет место асимптотическая эквивалентность:

Т_в(п) ~ T_vN(n) ~ T_opt(n) ~ п log₂ п ~ log₂ п\.

Коснемся нижних границ пространственной сложности алгоритмов сортировки. Если из всех этих алгоритмов выделить класс таких, кото­рые используют для перемещения элементов обмены (<—>), а не присва-

¹ Этот пример сообщил автору Е. В. Зима.

118 Глава 4. Нижняя граница сложности. Оптимальные алгоритмы

ивания (:=), то для этого класса единственной нижней границей, если говорить о функциях, принимающих неотрицательные значения, будет тождественно равная нулю функция, так как существуют, например, пузырьковая сортировка, сортировки простыми и бинарными встав­ками, не использующие дополнительных переменных того типа, к ко­торому относятся элементы сортируемого массива. (То, что требуются переменные для хранения значений индексов элементов, несуществен­но при изучении алгебраической сложности сортировки.) Алгоритмы, использующие присваивания для перемещения сортируемых элемен­тов, не могут, естественно, обойтись без дополнительного места для хранения хотя бы одной величины того же типа, что и элементы сор­тируемого массива, и одной из нижних границ будет функция, тожде­ственно равная единице. Если рассматривать все алгоритмы сортиров­ки вместе, то вновь единственная неотрицательная целочисленная гра­ница— это 0. В соответствии с этим определяются как оптимальные, так и оптимальные по порядку сложности алгоритмы.

Для произвольного класса .s4 оптимальный по порядку сложности алгоритм может и не существовать: если .s4 содержит всего два ал­горитма A_г,A₂ и при этом A_г имеет низкую сложность при четных значениях целочисленного размера входа n и высокую — при нечет­ных, а A₂ — наоборот, то, очевидно, ни A_ъ ни A₂ не будут опти­мальными в .s4 по порядку сложности (представим себе, что T_A = = (1 + (-1)n)n, T_A2 = (1 - (-1)n)n). В то же время, если допустить, что T_A =(2+(-1)ⁿn , T_A =(2-(-1)n)n, то T_A (n) = е(T_A (n)) (обе функ-ции имеют порядок n), и это говорит о возможности существования оптимального по порядку сложности алгоритма при отсутствии оп­тимального.