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

До сих пор мы исследовали сложность в худшем случае, теперь обра­тимся к сложности в среднем. Мы ограничимся ситуацией, когда при каждом фиксированном значении 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. Понятие сложности в среднем

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

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

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

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

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

T_A (s) = У C^TJx)PJx) s= V (max C_A^T (x))P s (x) =
„ „ x^eX_s

x <eX_s x<e X_s

= ^ T_A (s)P _s (x) = T_A(s) J] P _s (x) = T_A(s).

x e X_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

Глава 2. Сложность в среднем

и возможно дальнейшее упрощение выражения для сложности:

m -1 m -2

k =i l =о

Если рассматривать m = А(n) как размер входа бинарного алго­ритма вычисления aⁿ, n eN⁺, то сложность в среднем по числу умно­жений для этого алгоритма есть |(m - 1).

Таким образом, при больших m сложность в среднем бинарного алгоритма возведения в степень приблизительно равна трем четвер­тым сложности в худшем случае.

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

Асимптотический закон распределения простых чисел. Для

функции п(n), значение которой равно количеству простых чисел, меньших данного натурального n, справедливо асимптотическое ра­венство

я(n)~т n -. (5.3)

In n

Как следствие, вероятность того, что при выборе «наугад» одного

из целых чисел 1,2,..., n попадется простое число, асимптотически

1 1 равна 1—. ^х

ш n

Пример 5.2. Вновь вернемся к алгоритму пробных делений, пред­назначенному для распознавания простоты данного n ^ 2 (приме­ры 1.2, 4.1). Будем рассматривать в качестве размера входа битовую

¹ Предположение о справедливости этого закона распределения простых чисел вы­сказывалось, в частности, Гауссом и Лежандром. Впоследствии в 1850 г. Чебышевым было доказано, что для некоторых констант c и C

c—<к{n)<C —
In n In n

для всех достаточно больших n, и, более того, им было установлено, что можно поло­жить C = 1,10555, c = 0,92129. Асимптотическое равенство (5.3) было полностью дока­зано в 1896 г. независимо Ж.Адамаром и Ш. Валле Пуссеном. «После доказательства неравенств Чебышева в 1850 г. речь шла, казалось бы, только о более точном нахож­дении и сближении постоянных c и C. Однако асимптотический закон распределения простых чисел был доказан лишь полвека спустя, в самом конце XIX века, на основа­нии совершенно новых идей, предложенных Риманом...» [39]. В [39, гл. V] приводится

элементарное доказательство неравенств Чебышева для C = 6 и c = -. Полное доказа-

тельство асимптотического закона имеется, например, в [16].

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

длину т данного числа. На первый взгляд сложность в среднем этого алгоритма могла бы оказаться существенно меньшей, чем сложность в худшем случае, так как для многих входов затраты совсем невелики. Например, для четных входов достаточно одного деления и т. д. Для сложности в худшем случае по числу делений нами была установле­на экспоненциальная оценка в(2^т/'²). Существует ли d eN такое, что сложность в среднем алгоритма пробных делений как функция от т допускает оценку 0{m^d)? Мы видим, что для довольно обширного множества входов размера т алгоритм пробных делений работает быстро, и предположение, что для сложности в среднем существует такое число d, выглядит правдоподобным. На самом деле все обсто­ит не так, потому что среди всех натуральных чисел доля простых (для которых алгоритм пробных делений работает долго) достаточно велика. Оценка количества V{m) простых среди чисел

2^т-^г ^п<2^т

может быть получена из приведенной выше теоремы о распределении простых чисел: воспользовавшись тем, что

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