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

33

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

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

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

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

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

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

^Л 2'»-¹sCn<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(gW) имеем Т*(т) = ОД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 (каждый следующий элемент последовательности получаем возведением в квадрат преды-