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

V

Л

Рис. 3. Ориентированный граф.

Построение какого-то одного выходящего из данной вершины v вояжа может быть выполнено произвольным блужданием по непрой-денным ребрам графа, завершающимся в вершине, из которой не выходит непройденных ребер. Систематизация блужданий может со-

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

стоять в том, что, попав в некоторую вершину, мы выбираем для продолжения пути ребро, ведущее в вершину с наименьшим доступ­ным номером.

Определяемый этим алгоритмом вояж может захватить и все реб­ра— например, когда граф имеет вид кольца (на рис. 4 изображен такой граф, для которого | E | = | V | = 5). Входом алгоритма является

граф G и вершина v. Если мы рассматри-
3 ваем \ E | как размер входа, то для сложно-

сти любого алгоритма построения вояжа обязательно имеет место нижняя оцен­ка П(| E |)—ввиду, например, того, что для любого фиксированного | E | существу­ет граф, имеющий вид кольца. Возника­ет вопрос, можно ли обосновать верхнюю оценку O (| E |)? Если да, то в итоге это да­ло бы оценку в(| E\).

Рис. 4. Граф в виде кольца (любой вояж охватывает все ребра).

Для представления графов, не имею­щих кратных ребер, часто используются матрицы смежности. Матрица смежно­сти— квадратная матрица порядка | V |, состоящая из нулей и единиц (фактиче­ски, булева матрица), в которой элемент с индексами i,j равен единице, если и только если из i -й вершины выходит ребро в j -ю вершину. Такой способ представления действи­тельно удобен во многих задачах. Но когда речь идет о блуждани­ях по графу, при которых однажды пройденное ребро изымается из дальнейшего рассмотрения, более удобным оказывается представле­ние графа в виде массива a₁,a₂,...,a\_V\ списков смежных вершин. В списке a_i, i = 1, 2,..., | V |, в порядке возрастания содержатся номера вершин, в которые входят ребра, выходящие из вершины с номером i. Для графа, приведенного на рис. 3, имеем

a ₁ = (2,4), a ₂ = (2,3), a ₃ = (1,4), a ₄ = (), a ₅ = (6), a ₆ = (5), a ₇ = ();

для графа в виде кольца —

a ₁ = (2), a ₂ = (3),..., a_V_₁ = (V\), a_V = (1)

(в этом графе | V | = | E |). Представление в виде массива списков смеж­ных вершин возможно и для графов, имеющих кратные ребра; в этом случае номера вершин в каждом списке располагаются в порядке неубывания.

§ 3. Асимптотические оценки (два примера)

Начав вояж из вершины с номером v, мы смотрим, не пуст ли спи­сок a_v: если он пуст, то вояж закончен. Если же список a_v не пуст, пе­реносим первый его элемент (пусть это будет, например, i) в список вершин, через которые шаг за шагом проходит вояж; затем рассмат­риваем список a_i, если он пуст, то вояж закончен, иначе повторяем все то же самое, что проделывали в предыдущей вершине, и т.д.:

l:= cons (v, nil); i:= v;

while not null (a_i) do i:= car (a_i); l:= cons (i, l); a_i:= cdr (a_i) od

Мы здесь использовали операции над списками, применяемые в язы­ке Лисп: car — первый элемент списка, cdr — список после удале­ния первого его элемента, cons —вставка элемента в начало списка, null —предикат проверки пустоты списка, nil —обозначение пустого списка.

Затраты, связанные с удлинением пути на один шаг и с проверкой, не завершен ли вояж, ограничены сверху константой (эти затраты суть четыре операции над списками), длина всего пути не превос­ходит | E |, и затраты во всех случаях не превосходят произведения некоторой константы на | E |.

Список l содержит в обратном порядке все вершины, через кото­рые последовательно проходит вояж. Если желателен прямой поря­док, то надо перевернуть l:

l ^′:= nil;

while not null (l) do l ^′:= cons (car (l), l ^′); l:= cdr (l) od

Построение списка l ^′ потребует некоторых дополнительных опера­ций над списками, число этих операций не превзойдет произведения некоторой константы c на длину списка l, но эта длина не превосхо­дит | E |, следовательно, число операций на этом этапе не превзойдет

с\Е\.

Естественно считать пространственные затраты на хранение спис­ка с числовыми элементами пропорциональными длине списка. В случае, например, графа в виде кольца каждый из списков l и l ^′ имеет длину | E |+1.

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

C^(G,v)^c\E\,

(3.2)

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

где c —некоторая константа. Это неравенство выполнено для любого имеющего | E | ребер графа. Поэтому если значение | E | принято за размер входа (напомним, что сам вход—это граф и выделенная в нем вершина), то из (3.2) будет следовать T ^(.\ E \) ^c\E\, откуда

T _VL(| E |) = O (| E |). (3.3)

Вместе с указанной ранее оценкой П (\ E \) оценка (3.3) дает

T _VL(| E |)=e(| E |).

Нетрудно вывести аналогичную оценку и для пространственной сложности.

Если массивы списков смежных вершин используются в качестве представления ориентированных графов, то построение начинающе­гося с заданной вершины v вояжа в графе G = (V, E) возможно с по­мощью алгоритма, который при выборе числа \ E \ ребер в качестве размера входа имеет сложность 6(| E |) по числу операций над списка­ми. Эта же оценка имеет место для пространственной сложности, если считать, что пространственные затраты на хранение списка с числовыми элементами пропорциональны длине этого списка.

Если бы граф представлялся матрицей смежности, то мы для ис­пользуемого алгоритма не смогли бы получить оценку сложности 6(| E |), так как при блуждании по графу вход в каждую вершину сопровождается проверкой, есть ли непройденное до сих пор реб­ро, выходящее из этой вершины. Например, для графа в виде кольца при \ E | = | V | = n мы имеем матрицу смежности порядка n:

[О 1 0... (Л 0 0 1... 0

0 0 0... 1

1 0 0... О

Начиная вояж из первой вершины, мы потратим 2 + 3 +... + n + 1 = = П(n ²) сравнений элементов матрицы с единицей при поиске первых подходящих вершин.

Разумеется, базовые операции над списками и операции сравне­ния элементов матрицы смежности с единицей различаются по за­тратности (сравнение с единицей—это очень дешевая операция). Но какими бы ни были положительные c ' и c ", отражающие затраты на операцию сравнения с 1 и, соответственно, на операцию над спис­ком, неравенство c '\ E \ ² > c "\ E | будет иметь место для всех достаточно

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

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

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

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

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

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

А(п) =

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—7	8—15	16—31	32—63	64—127
п:
7?D(m):

(в строке т указывается битовая длина входа; в строке п указывает­ся диапазон, в котором располагаются значения п, битовая длина т которых равна числу в предыдущей строке; в строке п указывается одно из тех чисел этого диапазона, на которых достигается макси­мум числа делений; в последней строке указано значение сложности 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) / 2}j - 1 > j= 2^m ' ² - 2 = (J= - ^r)2 ^{m/ 2},

V2

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

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

и при т ^ 4 имеем

В то же время, в силу (4.1) очевидно, что для всех т

r;w < 2 ^m ' ²- i < 2 ^ffl' ².

Отсюда следует требуемое.

Исследуем общий вопрос о возможности перехода от оценок Т*(т) к оценкам Т_А{п) и наоборот для какого-либо алгоритма А, считая, что эти две сложности соответствуют одному и тому же способу учета затрат, но разным размерам входа —1| • || и || • ||*, принимаю­щим значения в N⁺, причем если ||х|| = п для некоторого входа х, то ||х||* = m = A(n) = Llog₂ п\ + 1. В таком случае, очевидно, выполнено

TUm)= max ТЛп). (4.2)

^Л 2 '» -¹ sC n< 2 '»

Ясно, что Т_А(п) несет более полную информацию о рассматривае­мом алгоритме А, чем Т*(т): значения T*(m), т = 1, 2,..., образуют подпоследовательность последовательности Т_А{п), п = 1, 2,... Поэто­му естественно, что переход от оценок для Т_А{т) к оценкам для Т_А{п) приводит к более грубому результату, чем тот, который может быть получен при изначальном рассмотрении размера ||х|| = п. Особенно это касается нижних оценок (пример 4.1 прямо указывает на это).

Лемма 4.1. Пусть f (х) —неубывающая функция вещественной пе­ременной. Тогда если T^W^fW, то Т_А{п) sS/(tog₂ п + 1).

Доказательство. Пусть тип фиксированы, 2^т-^г ^ п < 2^т, и пусть значение п таково, что

2^т-^г s= h < 2^т, (4.3)

и при этом

Г_А(п) = Г_А*(т). (4.4)

Используем неубывание /(х):

Т_А{п) s= Т_А{п) = Т*(т) s=/(т) =/(Llog₂ п\ + 1) s= /(log₂ п + 1). П

Лемма 4.2. Пусть g{x) —неубывающая функция вещественной пе­ременной. Тогда

(i) если T_A{n)^g{n), то T*_A{m)^g{2^m), (ii) если T_A{n)^g{n), то Т*_А{т) ^g{2^m-^x).

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

Доказательство. Пусть т фиксировано, 2™-¹ s= п < 2^т, и пусть зна­чение h таково, что выполнены (4.3) и (4.4). Используем неубывание

(i) T*_A{m) = T_A{h)^g{h)^g{2^m),

(ii) T*_A{m) = T_Am 2g(fO 2g{2^m-^x). U

Утверждения следующих двух теорем непосредственно следуют из доказанных лемм. (При рассмотрении асимптотической оценки, содержащей некоторую переменную, подразумевается, что значение этой переменной стремится к бесконечности.)

Теорема 4.1. Пусть f (х) — неубывающая функция вещественной переменной. Тогда если rj(m) = 0(/(m)), то Т_А{п) = 0(/(log₂ п + 1)); как следствие, при /(х+1) = 0(/(х)) имеем Т_А{п) = 0(/(log₂ п)).

Теорема 4.2. Пусть g{x) — неубывающая функция вещественной переменной. Тогда

(i) если T_A{n) = 0{g{n)), то T*(m) = 0(g(2^m)),

(ii) если r _A (n) = fi(g (n)), то Т*(т) = ВД2'"-¹)); как следствие,

при g (|) =fi(g W) имеем Т*(т) = ОД2^т)).

Существуют функции, для которых условие /(х + 1) = 0(/(х)) или g (§) =ⁿ(?W) не выполнено —например, /(х) = 2*², g (x) = 2\

Для рассмотренных в примере 4.1 сложностей T _TD(n), T _T*_D(m) си­туация выглядит следующим образом. Функция /(х) = 2^х/2 явля­ется возрастающей, и по теореме 4.1 из T*_D(m) = 0{2^т1²) следует Г_тп(п) = 0(2⁽¹°82"+¹) / ²) = 0(_Л/7Т). Рассматривая возрастающую функ­цию g{x) = 4~х, мы можем, применив теорему 4.2(i), вывести из T _TD(n) = O (vTT) оценку T _T*_D(m) = 0(V2^) = 0(2 ^{m/ 2}).

Получить из оценки T _T*_D(m) = П(2^{т / 2}) оценку T _TD(n) = П(л/н) мы не можем, так как последняя оценка не верна; это не противоречит доказанным утверждениям.

Пример 4.2. Идея бинарного алгоритма возведения а в целую неотрицательную степень п, называемого также алгоритмом повтор­ного возведения в квадрат (мы будем обозначать его буквами RS, от английского названия алгоритма repeated squaring — повторное воз­ведение в квадрат), состоит в том, что если двоичная запись п есть 13_к...13_г13₀, то вычисление а^п может быть сведено к вычислению после­довательности значений ^=а⁽²', i = 0,l,...,k (каждый следующий элемент последовательности получаем возведением в квадрат преды-

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

дущего), и подсчету произведения и тех q, для которых /3; = 1:

q:=a; и:=1;

for i = 0 to fc-1 do

if /3 i = l then u:=u-q fi;

q:= q ² od u:=u- q

Например, a ¹¹ = a ⁸ • a ² • a (5 умножений), так как (11)₁₀ = (1011)₂.

Займемся сложностью по числу умножений этого алгоритма. Ис­пользуя А(п) для обозначения битовой длины п и обозначение А*(п) для числа единиц в двоичной записи п, мы легко получаем следующее.

Если рассматривать п как размер входа бинарного алгоритма вы­числения а^п, n eN+, то сложность T _RS(n) по числу умножений для этого алгоритма равна А(п) + А*(п) - 2. Если в качестве размера вхо­да рассматривать т = Х{п), то сложность Т^{т) по числу умноже­ний равна 2т - 2.

Для 7^_s(m) и T _RS(n) имеем очевидные асимптотические оценки

r_R*_s(m) = e(m), r_RS(n) = e(log n).

Заметим, что мы не можем вывести из 7^ (т) = 2т - 2 равенство T _RS(n) = A(n) + A*(n) - 2, хотя обратный вывод очевиден.

В рассмотренном алгоритме предполагается, что показатель сте­пени п задан как массив двоичных цифр. Если показатель п задан как число, то его двоичные цифры 13₀,13_г,... могут быть получены одна за другой нахождением соответствующих частных и остатков от де­ления на 2. Это не изменит оценок 6(log n), 6(m) как для общего числа операций, так и для числа мультипликативных операций. Но при этом бинарный алгоритм возведения в степень может быть ис­пользован, например, для вычисления А^п, где А —матрица большого порядка и т. д. В этом смысле те операции, которые подразумевают­ся в командах u:=u-q и q:=q², естественно подсчитывать отдельно и именно их считать составляющими главные затраты алгоритма.

Задачу вычисления а^п в некотором множестве с ассоциативным умножением (т. е. в полугруппе) часто формулируют как задачу об ад­дитивных цепочках для п, т. е. о наборах целых чисел п_г < п₂ <... < п_к, в которых

• п_г = 1, п_к = п;

• для каждого i, 1 < i ^ к, найдутся s, t такие, что l^ t ^ s<i и щ + + n_s = щ.

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

Каждая аддитивная цепочка для n задает способ вычисления aⁿ. На­пример, аддитивная цепочка 1,2,3,4,8,11 для 11 задает тот спо­соб, который соответствует бинарному алгоритму возведения в сте­пень. Задача быстрого возведения в степень n с помощью умноже­ний—это фактически задача построения короткой аддитивной це­почки для n.

Обозначение l (n) закреплено за длиной самой короткой аддитив­ной цепочки для n. Бинарный алгоритм возведения в степень ис­пользует свою специфическую аддитивную цепочку (назовем ее би­нарной). Бинарная цепочка не для всех n имеет длину l (n) (см. за­дачу 19). Но, как мы выясним несколько позже, длина бинарной це­почки и l (n) имеют одинаковый порядок. Помимо этого бинарные цепочки легко и быстро строятся, чего в общем случае нельзя ска­зать об аддитивных цепочках длины l (n).

Некоторые предположения относительно функции l (n) до настоя­щего времени не доказаны, хотя и подтверждены проверкой для мно­гих n. К числу таковых относится, например, гипотеза Шольца—Брау-эра: l (2 n -1)^ n -1 + l (n) для всех n > 0. ^г

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