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

111

ства а = 0, b = c = 1, d = n-2. После первого сравнения на протяже­нии всего выполнения алгоритма постоянно будут иметь место нера­венства Ъ^1,с^1.

Все сравнения, совершаемые при выполнении алгоритма V, мож­но разбить на типы, обозначаемые AA,AB,AC,AD, BB,BC,BD,CC, CD,DD, например: сравнение принадлежит типу АВ, если один из сравниваемых элементов берется из А, другой—из В, и т. д. Исходя из этого, можно выписать все возможные изменения четверки (а, Ь, с, d) под действием сравнений разных типов:

1,b,c,d + 1), 1,b,c,d + 1), 1,b,c + 1,d),

АА: (а-2, b + 1,c + 1,d), АВ: (a-1,b,c + 1,d)|(a АС: (а-1, b + 1,c,d)|(a AD: (а - 1, Ъ + 1, с, d) | (а

BB: (a, b - 1, c, d + 1), BC : (a, b - 1, c - 1, d + 2) | (a, b, c, d), BD: (a, b - 1, c, d + 1) | (a, b, c, d), CC : (a, b, c - 1, d + 1), CD: (a, b, c - 1, d + 1) | (a, b, c, d), DD: (a, b, c, d) (вертикальная черточка здесь означает «или»). Рассмотрим функцию

= -2а + Ъ + с 3

2. Для начальной и конечной стадий имеем

L(a, b, c, d)

n —

2)=0 соответственно.

I(n,0,0,0) = ³₂n-2 и 1(0,1,1,

Каждое сравнение типов AA, BB, CC понижает значение L на 1, т.е. дает ∆L =-1. Выпишем все возможные значения ∆L при выпол­нении сравнений различных типов:

-1, — 1 | 0,

-³₂i-¹₂,

—2 | 0,

_1 2, 0.

AA, BB, CC : BD, CD :

AB, AC : BC : AD : DD :

Сравнения, относящиеся к типам AB, AC, BC, могут приводить к ∆L <-1, но это не может быть гарантировано никаким специ­альным выбором элементов из соответствующих множеств четверки

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

(A, B, C, D), даже если принимать во внимание результаты всех срав­нений, в которые были вовлечены конкретные элементы этих мно­жеств. Например, сравнение типа AB в том случае, когда выбранный элемент из A оказывается больше выбранного элемента из B, преоб­разует (a, b, c, d) в (a - 1, b,c,d + 1), что дает ДL < -1. Но результаты предшествующих сравнений не дают оснований для отметания воз­можности того, что выбранный элемент из B равен шах{x₁, x₂, •••, x_n} (ибо этот элемент оказался большим во всех сравнениях, в которые

он был вовлечен). Но тогда будет выполнено ДL = -¹₂. Аналогичным образом дело обстоит для сравнений, принадлежащих типам AC, BC. Поэтому, рассматривая поведение алгоритма V в худшем случае, на­до считать, что на всех этапах ДL ^ - 1. Но тогда для достижения ра­венства L(a, b, c, d) = 0 потребуется не менее \L(n, 0, 0, 0)1 сравнений. Это значит, что общее число сравнений в худшем случае не меньше,

чем -_n - 2. □

Представленный в приложении A алгоритм одновременного поиска наибольшего и наименьшего элементов массива, требующий в худшем

случае не более -2 - 2 сравнений, является оптимальным^г.

Наряду с алгоритмами поиска наименьшего элемента, бинарно­го поиска места элемента в упорядоченном массиве и алгоритма од­новременного поиска наибольшего и наименьшего элементов мас­сива примером оптимального алгоритма может служить алгоритм («схема») Горнера вычисления значения полинома в данной точке (см. приложение D).

Для произвольного класса .s4 оптимальный алгоритм может и не существовать: если, например, .s4 содержит ровно два алгоритма, A₁,A₂, и при этом A₁ имеет низкую сложность при четных значе­ниях целочисленного размера входа n и высокую — при нечетных, а A₂ — наоборот, то, очевидно, ни A₁, ни A₂ не будут оптимальны­ми в .s4. Ясно, что если оптимальные алгоритмы в классе .s4 су­ществуют, то их сложности совпадают: из неравенств T_A (n) ^ T_A (n) и T_{A 2} (n)^T_{A 1} (n) следует, что T_{A 1} (n) = T_{A 2} (n). Несколько более содер-жательный пример можно найти в задаче 76.

В отличие от поиска наименьшего элемента, поиска места в упо­рядоченном массиве и одновременного поиска наибольшего и наи-

¹ Этот алгоритм и идея использования четверок ( A, B, C, D) в доказательстве его оп­тимальности были предложены И. Полом в [56], но при этом убывающие функции в его доказательстве не привлекались, из-за чего потребовались дополнительные словесные мотивации.