§ 15. Оптимальные алгоритмы

113

меньшего элементов, задача сортировки не столь проста: те алгорит­мы, которыми пользуются на практике для ее решения, не являются, строго говоря, оптимальными (см. приложение F).

Заметим при этом, что для каждого конкретного п за конечное число шагов может быть найдено наименьшее число сравнений, до­статочное в худшем случае для сортировки п элементов, а вместе с ним и алгоритм сортировки с такой сложностью. Это следует из то­го, что при каждом конкретном п алгоритм сортировки может быть представлен бинарным деревом. Можно порождать одно за другим все бинарные деревья с высотой, не превосходящей [log₂n!l, в вер­шинах каждого такого дерева различными способами расставлять вы­ражения вида x_t<Xj, где i,j^n, а в листьях — различные переста­новки длины п. Для каждого размеченного таким способом дерева нужно проверить, действительно ли каждая ветвь приводит именно к тому порядку, который указан в листе, и что все возможные поряд­ки охвачены. Из всех «правильных» деревьев выбирается имеющее наименьшую высоту. Оно определяет оптимальный алгоритм для за­данного п.

Таким образом, мы имеем алгоритм, который, исходя из п > 0, строит оптимальный по числу сравнений алгоритм сортировки мас­сивов из п элементов (алгоритм строит алгоритм). Этот алгоритм построения оптимального алгоритма сортировки требует огромной работы, даже если применить все средства экономии перебора. Этот пример еще раз показывает, что понятие алгебраической сложности требует осторожного обращения, —объем неучитываемых операций может превзойти разумные пределы.

Бинарный алгоритм возведения в степень п также не является оптимальным по числу умножений при использовании п в качестве размера входа (см. задачу 19), хотя и легко показать, что для слу­чая п = 2^к при рассмотрении к в качестве размера входа оптималь­ность имеет место: из предложения 14.5 следует, что возведение в сте­пень п = 2^к не может быть выполнено с затратами меньшими, чем к умножений, а бинарный алгоритм обходится в точности этим чис­лом умножений.

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

Если затраты для каждого входа являются целыми числами (на­пример, они являются количеством выполненных операций), то для фиксированного размера п₀ входа в рассматриваемом классе .s4 ал-

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

горитмов решения некоторой задачи P существует такой, сложность которого при n = n₀ есть минимум сложностей всех алгоритмов из .s4. Можно определить такой минимум для любого значения n, получа­емую таким способом функцию от n иногда называют сложностью задачи P по отношению к классу алгоритмов .s4. Важно, что при раз­ных n минимумы могут доставляться разными алгоритмами из .s4 (см. задачу 76). В дальнейшем мы не будем касаться этих вопросов.