§ 4. Длина числа как возможный размер входа

31

больших |Е|. Константы, скрытые в оценках П(\Е\²) и 0(|Е|), най­денных для сложностей алгоритма при использовании двух разных способов представления графа, различаются между собой. Но тем не менее мы можем сравнивать рост первой и второй сложностей на ос­нове этих оценок. Этот пример показателен и в том отношении, что «дешевых» операций может быть слишком много (их число может слишком быстро расти при увеличении раз­мера входа) и их игнорирование может дать неправильное представление о реальной вре­менной сложности алгоритма.

Рис. 5. Граф с одной вершиной и произ­вольным заданным числом ребер.

Если рассматривать два параметра |V|, |Е| размера входа, то сложностью алгоритма VL будет функция 7^(1П \Е\) двух переменных. Для того чтобы устанавливать для нее асимп­тотические оценки, эта функция должна быть определена для всех (или, по крайней мере, всех достаточно больших) натуральных значе­ний |V|, \L\. Это значит, что для всех таких |V|, |Е| должен существовать граф, имеющий |V| вершин и\Е\ ребер. Проблема будет сня­та, если, например, допустить к рассмотрению и такие ориентированные графы, которые

имеют кратные ребра. Оценка 7^(1 V|, \Е\) = 0(|Е|) будет, очевидно, выполняться. Можно обосновать и оценку T^(\V\,\E\) = П(\Е\): до­статочно рассмотреть имеющий |Е| ребер граф в виде цветка (рис. 5), добавив к нему |V| — 1 изолированных вершин (подобных вершине 7 на рис. 3) и взяв в качестве v вершину в центре «цветка». В итоге ^(|Щ£|) = в(|Е|).

§ 4. Длина числа как возможный размер входа

Часто, хотя и не всегда, для алгоритмов целочисленной арифметики, входом которых является целое неотрицательное число п, размером входа выбирают не само п, а его битовую длину, или, иными слова­ми, количество А(п) цифр в его двоичной записи:

А(п) =

1,

Llog₂ п\ +1,

если n= 0, если n> 0.

Выражение Llog₂ п\ + 1 во второй строчке этого определения можно заменить на [log₂(n + 1)1 — см. задачу 2.

32 Глава 1. Сложности алгоритмов как функции числовых аргументов

Пример 4.1. Вернемся к алгоритму пробных делений (пример 1.2). Наряду с его уже рассмотренной сложностью T_TD(n) введем еще одну сложность (также по числу делений) T_T*_D(m), m = A(n). Легко обнару­жить, что эта новая функция ведет себя не так, как функция T_TD(n), для которой характерны резкие скачки. Для начальных значений т имеем

т:	2	3	4	5	6	7
п:	2—3	4—7	8—15	16—31	32—63	64—127
п:	3	7	13	31	61	127
7?D(m):	1	1	2	4	6	10

(в строке т указывается битовая длина входа; в строке п указывает­ся диапазон, в котором располагаются значения п, битовая длина т которых равна числу в предыдущей строке; в строке п указывается одно из тех чисел этого диапазона, на которых достигается макси­мум числа делений; в последней строке указано значение сложности Tj_D(rri)). В поведении 73^(т) не видно резких скачков. Переход от размера ||п|| = п к размеру ||п||* = т = А(п) влечет более основатель­ное преобразование функции Т{п), чем простая замена переменной. Теперь одним и тем же размером m обладают несколько входов п, затраты для которых, вообще говоря, различны, и, в соответствии с определением сложности, мы должны брать максимум этих затрат. Данным размером m обладают все целые п такие, что

2^m-¹^n<2^m. (4.1)

Согласно постулату Бертрана, при m > 1 в таком диапазоне обяза­тельно встретится простое число.

Постулат Бертрана.^г При любом целом N > 1 имеется простое число, принадлежащее интервалу (JV, 2JV).

С помощью постулата Бертрана мы можем доказать, что T*_D(m) = = 6(2^m/2). В самом деле, обозначим через р_т наибольшее простое число битовой длины т. Количество делений, требующееся алго­ритму для работы с р_т, будет равно LVP^J - 1- В силу (4.1) имеем _L2&"-U/2j - 1 ss LVP^J - 1. Таким образом,

T*D(m) > L2^(m-^1)/2j - 1 > j=2^m'² - 2 = (J= - ^r)2^m/2,

V2

¹ Сформулирован Ж.Бертраном в 1845 г. и доказан П.Л.Чебышевым в 1852 г. Об­суждение доказательства выходит за рамки этого курса, доказательство Чебышева см. в [38] (статья «О простых числах»). Доказательства, использующее лишь элементар­ные средства, можно найти в [35] (приложение «Доказательство постулата Бертрана (теоремы Чебышева)») и в [11, § 5].