§ 17. Нижняя граница сложности в среднем 125

для которого h_ko = 1 - Т7-. Это дает нам

Е^ТгЛ =Е(т-1) + 1--^,

4=i

и с помощью следующего из теоремы 17.1 соотношения

4=i

мы находим

Е(т-1) + 1--^^|п-2.

После упрощения получаем

Ет=г|п-2 + -^.

Таким образом, все доказано и для четных, и для нечетных п. □

Если существует алгоритм решения рассматриваемой задачи, ко­торый требует ровно (17.1) сравнений, то, по только что доказанно­му предложению, этот алгоритм является оптимальным в среднем по числу сравнений. Укажем такой алгоритм. Если п четно, то действуем в соответствии с алгоритмом, обсуждавшимся в примере 15.1. Пусть п = 2к + 1, к ^ 0. Находим

тл; = min{x_2i_₁, x_2i}, M_t = max{x_2i_₁, x_2i},

i = l,2,...,fc, и

m = min{m₁,m₂, ...,mj,

что потребует n - 2 сравнений. Без дополнительных затрат можно найти s, 1 ^ s ^ 2fc, такое, что т = m_s. Далее сравниваем х_п (т. е. х_2к+1) c M_s. Согласно рассуждениям, проведенным выше при анализе срав­нений типа АВ, вероятность того, что х_п > M_s, равна -- - -—. Если х_п > M_s, то результатом работы алгоритма будет

max{M_l5..., М_$__ъ M_s+1,..., М_к, х_п}, т,

в противном случае —

max{M₁,M₂, ...,MJ, min{m,x_n}.

Среднее число сравнений при нечетном п равно

(п-2) + (|--У +2(| + ^) + (^ILy^"1)=|n"2 + ^' что и требовалось.

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

Существует оптимальный в среднем алгоритм одновременного на­хождения наибольшего и наименьшего элементов массива длины n, n ^ 2, с помощью сравнений. Этот алгоритм имеет сложность (17.1).

§ 18. Нижние границы сложности рандомизированных алгоритмов. Принцип Яо

Этот параграф начнем с формулировки и обсуждения одного факта из теории игр. С произвольной квадратной числовой матрицей M = (m_ij) порядка k связывается матричная игра двух игроков, которых мы на­зовем I и J. Один раунд игры состоит в том, что I и J независимо друг от друга называют соответственно целые i и j из диапазона от 1 до k, и после этого J выплачивает своему сопернику I сумму в m_ij рублей (при m_ij < 0 сумма в -m_ij рублей выплачивается игроком I игроку J). Стратегией называется вектор p = (p_ъ p₂, ■■■,p_k) с веще­ственными неотрицательными компонентами, в сумме дающими еди­ницу; стратегии (1, 0,..., 0), (0,1,..., 0),..., (0, 0,..., 1) называются чи­стыми. Допустим, что игроки независимо избирают для себя некото­рые стратегии—обозначим их соответственно p и q,—и затем в по­следовательных раундах игрок I называет число i с вероятностью p_i , а игрок J называет число j с вероятностью q_j. Математическое ожи­дание выигрыша игрока I равно, как нетрудно подсчитать,

mijpiqj>

i j

эту величину мы будем обозначать M{p, q). Допустим также, что вме­сто проведения большого числа раундов игры каждый из игроков, основываясь на известной матрице M, один раз выбирает, незави­симо от другого игрока, для себя некоторую стратегию и сообщает ее судье, который по полученным от игроков стратегиям (векторам p и q) вычисляет M{p,q), умножает его на количество предполагав­шихся раундов и объявляет полученное число выигрышем игрока I. Естественно, что игрок I заинтересован в нахождении такой страте­гии, которая максимизирует M{p,q), а у игрока J цели прямо про­тивоположные. Одна из теорем раздела теории игр, посвященного матричным играм¹, утверждает, что для игроков существуют опти­мальные стратегии p*,q* такие, что M{p*,q*) является одновременно значением величин

maxminM(p,q) и min max M(p,q).

p q q p

¹ См., например, [7, теорема 2.1].