Глава 2

Сложность в среднем

§ 5. Понятие сложности в среднем

До сих пор мы исследовали сложность в худшем случае, теперь обра­тимся к сложности в среднем. Мы ограничимся ситуацией, когда при каждом фиксированном значении s размера входа сами соответству­ющие входы образуют конечное множество X_s = {x: ||x||=s}. Будем предполагать, что каждому xeX_s приписана некоторая вероятность P _s ( x):

О ^ P _s ( x) О,

и при этом

Таким образом, при каждом допустимом значении s размера входа множество X_s превращается в вероятностное пространство; по умол­чанию считается, что вероятность распределена равномерно:

P_s(x) = J-, (5.1)

где N_s—количество элементов множества X_s. Функции от s

^ C^T_A(x)P _s ( x) и ^ C_A^S(x)P _s ( x) (5.2)

называются временной и, соответственно, пространственной сложно­стью в среднем алгоритма A. Более подробно:

Определение 5.1. Пусть при любом допустимом значении s мно­жество X_s всех входов размера s является вероятностным простран­ством, в силу чего временные и пространственные затраты алгорит­ма A для входов x (т. е. C^T_А(x) и C^S_A(x)) размера s являются случайны­ми величинами на X_s. Сложностью в среднем называется математиче­ское ожидание (первая или вторая сумма из (5.2)) соответствующей случайной величины.

§ 5. Понятие сложности в среднем

43

Сложность в среднем может принимать и нецелые значения, даже если функция затрат целочисленна.

Для временной и пространственной сложностив среднем алгорит­ма A мы будем использовать обозначения T _A(0, S_A{-).

Теорема 5.1. Для любого алгоритма A при любом распределении вероятностей на множестве X_s, где s — некоторое допустимое зна­чение размера \\ ■ \\, сложность в среднем не превосходит сложности в худшем случае:

T_A(s)sST_A(s), S_A(s)^S_A(s).

Доказательство. Докажем, например, первое неравенство:

T_A(s) = У C^TJx)PJx) s= V (maxC_A^T(x))Ps(x) = „ „ x^eX_s

x<eX_s x<eX_s

= ^ T_A(s)P_s(x) = T_A(s) J] P_s(x) = T_A(s).

xeX_s x^X_s

Второе неравенство доказывается аналогично. □

Ниже в этом параграфе мы рассмотрим временную сложность в среднем ряда алгоритмов.

Пример 5.1. Как было уже установлено (пример 4.2), бинарный алгоритм возведения в степень n требует А(n)+А*(n)-2 умноже­ний; если в качестве размера взять m = A(n), то сложность в худшем случае будет равна 2m - 2. Подсчитаем сложность в среднем, привле­кая m как размер входа. Всего имеется 2^{m -1} неотрицательных целых битовой длины m; если считать все эти числа равновероятными, то искомая сложность есть

2^m-l 2^m-l

_{m -} Yt (A(n) + A*(n)-2) = m-2+_{m -r} ^ A*(n).

n=2^m-¹ n=2^m-¹

Первая цифра каждого из чисел битовой длины m равна 1; коли­чество чисел, имеющих кроме старшей цифры еще k, 0^k^m-1,

ненулевых двоичных цифр, равно f^m ) (т. е. числу сочетаний из

m - 1 по k). Поэтому искомую сложность можно переписать в виде

k=i '- ^Л

то при 1 ^ k ^ m - 1 выпол

k(^m-¹) = (m-i)(m_-^-₁²),

Легко проверяется, что при 1 ^ k ^ m - 1 выполнено

k-1

44