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

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

m -1 m -2

k=i l=о

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

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

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

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

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

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

Inn

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

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

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

шn

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

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

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

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

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

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

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

45

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

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

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

от

7г(2^т) ~ . —, т—>оо₅ а также равенством V{m) = п{2^т) - п{2^т-^г), получим

Теперь уже экспоненциальность роста сложности в среднем алго­ритма пробных делений выводится легко. Обозначим через D{n) количество делений, требующееся алгоритму пробных делений при­менительно к натуральному числу п. Для любого простого р ^ ^ 2^т-^г, т^7, выполнено D{p) > 2^т1^^х (в самом деле, D{p) = LVpJ - 1 Z L2^(m-^1)/2J - 1 > 2&"-«/² - 2, и при т ^ 7 выполнено

;m-l)/2 ПШ/2-1 ТЛ

2^т — 1

на ^гт 2 D{n). При ^т ^ 7 мы имеем

2^{(m 1)/2} - 2 ^ 2^{т12 г}). Интересующая нас сложность в среднем рав-1

= 2Г71-1

2^т-1

1

Т.	D(n)^	1 ГП-1		Т.
=2т-1			2^mp	-Чр<2^т— простое

_2т_₁ „,! D{p)^V{m)2-^ml2. (5.5)

2ГП-1

Учитывая (5.4), находим, что последняя величина при т —»оо асимп­тотически равна

1 от/2

(21п2)т '

46