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

I

I

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

мы находим

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

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

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

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

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

тл; = min{ x _{2 i} _₁, x_2i}, M_t = max{ x _{2 i} _₁, x_2i},

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

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

что потребует 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 ₂,..., M J, min{ m, x_n }.

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

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

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

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

Этот параграф начнем с формулировки и обсуждения одного факта из теории игр. С произвольной квадратной числовой матрицей 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*) является одновременно значением величин

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

p q q p

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

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

В дальнейшем нас не будут интересовать оптимальные стратегии, од­нако равенство

max min М{р, q) =min max M{p,q) (18.1)

p q q p

окажется для нас очень ценным.

При фиксированной стратегии р значение min M{p,q) равно ми-

q

нимальному значению среди

/_, milPi> У_.Щ2Р1> ■■■> / ,mikPi>
i i i

т.е. mm^ mijPi (в качестве стратегии q, на которой достигается ми-

разом тахМ(р, о) = max У] т.-.-о,-. Это позволяет переписать равен- Р i j ' '

нимум, выступает некоторая чистая стратегия). Аналогичным об­разом max M{p,q

р

ство (18.1) в виде

max min V т_ир₍ = min max V т^а_и (18.2)

p j 1—1 ' q i 1—1 ' '

i j

откуда следует, что для любых стратегий р = {р_ъ р₂,..., р_к) и q = (q _ls q2,---,4k) выполнено

min V т_;,р;^ max V m;,о,. (18.3)

i j

То, что исходная матрица квадратная, не играло никакой роли в вы­воде последней формулы, каждая из переменных i и j могла пробе­гать свое множество значений. Можно даже не нумеровать строки и столбцы исходной матрицы, а дать им какие-то имена. Для мат­риц с такого рода именованием строк и столбцов чаще используют название таблица.

Вернемся теперь от матричных игр к анализу сложности алго­ритмов. Пусть имеется конечное множество .s4 алгоритмов решения некоторой задачи и конечное множество X входов фиксированного размера, и для них составлена числовая таблица, элементы которой проиндексированы элементами множества X (первый индекс) и мно­жества .s4 (второй индекс). В качестве элемента таблицы с индекса­ми х,А берется величина затрат (например, временных) С_А(х). Если рассмотреть какие-либо распределения вероятностей на X и .s4, то в силу (18.3) будем иметь

min Е_хС_А(х) s= max Е^С_А(х), (18.4)

Дата добавления: 2014-01-11