§ 13. Нецелые размеры входа и непрерывные оценочные функции 97

ся следствием формулы Стирлинга (см. § 9). Это дает нам оценку

6(Lv n³ + 1J logLv n³ + 1J) для интересующих нас затрат. После упро­щения получаем в(n^3/2 logn). В этом примере затраты однозначно определяются по n, поэтому полученная оценка определяет асимпто­тику сложности рассматриваемого алгоритма при использовании n в качестве размера входа.

Оценку O(L\/n³ + lJ logL\/n³ + lJ) и, тем самым, O(n^3/2 logn) мож­но было бы получить не прибегая к формуле Стирлинга, исходя из того, что сумма конечного числа неотрицательных слагаемых не пре­восходит произведения наибольшего слагаемого на число слагаемых суммы. Для в этот прием не работает, как показывает пример суммы

2 2i.

i=i

§ 13. Нецелые размеры входа и непрерывные оценочные функции

Предложение 13.1. Пусть для некоторого алгоритма A можно указать входы v₀,v₁, ..., размеры которых ограничены сверху и снизу положительными константами c_г и c₂:

ci^l|vil|^c₂, i = 0,l,...,

и в то же время затраты C_A(v_i) неограниченно возрастают при i -» оо. Тогда не существует такой непрерывной на отрезке [c_ъ c₂] функции f(x) вещественной переменной, что T_A(x)^f(x) для всех значений x размера входа, принадлежащих отрезку [c_ъc₂].

Доказательство. Очевидно, что T_A(||vi||) ^ C_A^T{v_i), и поэтому по­ следовательность T_A(||vi||), i = 0,l, ..., не ограничена. В то же время, любая функция f, непрерывная на [c₁,c₂], ограничена на этом от­ резке. □

Сформулируем еще одно столь же легко доказываемое утвержде­ние (доказательство опускаем).

Предложение 13.2. Пусть A —некоторый алгоритм, и f(x) — функция вещественной переменной, определенная на некотором ин­тервале I. Пусть T_A(x) ^f(x) всякий раз, когда xеI и значение T_A(x) определено. Пусть x₀ е I и для любых ǫ > О, N > 0 найдется такой вход v алгоритма A, что |x₀ - ||v|| \<ǫ и C^T_A{v) >N. Тогда f(x) раз­рывна в точке x₀.

98 Глава 3. Оценивание числа шагов (итераций) алгоритма

Пример 13.1. Вновь рассмотрим алгоритм Евклида, используя те­перь в качестве размера входа (а_п, а-.) рациональное число —, кото-рое, как указывалось в примере 9.1, однозначно определяет соответ­ствующее количество делений с остатком (сложность Tl — ], соот-

^ь aj

ветствующая этому размеру, совпадает с затратами: С_Е{а₀,а_г)). В си­лу формулы Бине (10.2) имеем

lim Щ^ = Ф,

при этом C_E(F_n+1,FJ = n. Поэтому если функция вещественной пе­ременной f{x) такова, что C_E(a₀,a_i) «S/f—1, то, в силу предложе-

ния 13.2, /(х) разрывна в точке ф. Мы воспользовались тем, что для любого е > 0 и любого натурального JV найдется рациональное число

u/v такое, что | ф - - | < е и С_Е{и, v) =г JV. v Можно доказать, что здесь дело не в числе ф—то же самое спра­ведливо для любого х₀ > 1. Пусть 0 < s < х₀ - 1. Докажем, что в раци­ональных точках е-окрестности V_Xot£ числа х₀ функция Г_Е(г) не явля­ется ограниченной. Предположим противное: пусть г = — е V_Xot£ —ра­циональное число, на котором достигается максимум. Пусть частные, возникающие в процессе применения алгоритма Евклида к щ, и_ъ равны q_ls q₂,---,q_n:

Щ-1 = Ч1Щ + Щ+ъ i = l,2, ...,п, и_п+1 = 0.

Выберем 5 > 0 столь малым, что V_r>5 с V_Xo>s, и возьмем любое s е Q \ Z

такое, что - - s < 5 (легко заметить, что - = q„sZ). Пусть и_п и_п

I, т—такие целые, что s = —. Используя g-i,g?, ...,о,,, найдем v_n, v-,,

, v_n gN⁺, для которых

v;-i =^aivi +vi+i, i = l,2,...,n,

и v_nx = 1, v_n = т. Индукцией по к легко доказать, что для к = 0,1, , _- - 1

< 5. (13.1)

"n-fc

В самом деле, для к = 0 это очевидно; остается показать, что при 0<к<п-1из (13.1) следует

"nk1

< 5. (13.2)