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

П п п

Со

Со

Со

При этом ряд 2 7—-L i _ iir— Т_i) расходится: члены этого ряда поло-

жительны, и i -й член есть в- (является величиной порядка -).

-) (является величиной порядка -Отсюда математическое ожидание (11.2) равно бесконечности.

Пусть теперь u вопросов (будем считать, что это вопросы с но­мерами 1,2,..., u) имеют кратность 1, а остальные n — u вопро­сов—кратность большую, чем 1, и пусть u ^2. Оказывается, что при стабильных неправильных ответах обучаемого на задаваемые вопро­сы математическое ожидание времени, проходящего до получения всех, кроме какого-то одного, вопросов с номерами 1,2,..., u, есть конечная величина. Докажем конечность среднего времени ожида­ния какого-нибудь одного вопроса с номером от 1 до u, далее можно применить индукцию. Вероятность получить такого рода вопрос по­сле i вопросов с номерами из диапазона от u + 1 до n полностью определяется значениями u,m,i:

m-u m-u+1 m-u+i- l u m ' m+1 '" m + i-1 ' m + i

Эта вероятность при i > u равна

u (m - u)(m - u +l)...(m -l)

- u + l)...(m -

(m - u + i)(m - u + i + l)...(m + i -l)(m + i)

Поэтому искомое математическое ожидание есть сумма некоторого конечного числа слагаемых и ряда

v-< u (m - u)(m - u + l)...(m - l) _f i ^

2-1 (m - u + i)(m - u + i + 1)... (m + i - 1)(m + i) ^{U J}'

i=u+l или

u (m - u)(m - u + l)...(m -l) V 7------------ ------ ^{i + 1} „------------- -■.

' i—i (m-u + i)(m-u + i + l)...(m + i)

i=u+l

Упрощая, получаем

j + u+1

u (m - u)(m - u + 1)...(m -1)У

j ^ (j +m)(j + m + l)...(j + m + u)

§ 12. Вложенные циклы (дополнительные примеры)

Ряд, входящий в это выражение, сходится, так как j -й член ряда есть ®(- _ju ] и u^2.

Это рассуждение сохраняет силу и в том случае, когда вопросы с номерами 1,2,..., u являются одним и тем же вопросом, что поз­воляет отметить следующую характерную черту алгоритма кратных карт:

Если изначально все вопросы имеют кратность 1 и обучаемый да­ет на все вопросы неправильные ответы, то математическое ожи­дание времени до наступления момента, к которому обучаемый по­лучит хотя бы по одному разу каждый из вопросов, равно бесконечно­сти, хотя вероятность наступления такого момента равна 1. Если же изначально все вопросы имели большие единицы кратности (на­пример, все они имели кратность 2), то обсуждаемое математиче­ское ожидание конечно.

§ 12. Вложенные циклы (дополнительные примеры)

При анализе сложности вложенных циклов мы естественно приходим к вычислению и оцениванию кратных сумм.

Пример 12.1. Число обменов при транспонировании (n х n)-мат-рицы (a_ij)

for i = l to n -1 do

f or j = i + 1 to n do a_ij <-> a_ji od od

n -1 n n -1 2

есть Xi Xi 1 = 2 (n - 0 = _-. Аналогично, распознавание сим-

i = l j=i+l i = l

метричности данной (n x n)-матрицы требует в худшем случае срав­нений в количестве ^- X1 = ^- (n - i + 1) = ⁽ n ^{+ n} - ²⁾ и т. д.

i =l j=i i = l

Легкое получение ответов в примере 12.1 объясняется тем, что в выписанных формальным путем суммах нижние границы суммиро­вания не превосходили верхних; в таких случаях всегда, например, ^q

X 1 = q - p + 1. Но, получая сумму этим формальным путем из опе- j=p ратора цикла, можно столкнуться с тем, что p> q (оператор цикла

затратит 0 шагов), и ответ q-p + 1 будет неправильным. Соответ­ствующий пример дается в задаче 71.

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

Подходя к асимптотическим оценкам, отметим один простой, но полезный факт.

Предложение 12.1. Пусть А —один из символов О, Q, П. Пусть а{к), Ъ(к) определены для всех fceN+ и принимают положительные значения (не обязательно целые); пусть a (fc) = Л(Ь(Щ к -»°°. Тогда

f, а(к) = а(f, Ъ(к)\ п-»°°. Утверждение остается справедливым

fc=i fc=i

и при замене верхней границы суммирования п на у(п) Э ля любой

функции ip(nl определенной для всех n eN+ и принимающей значения

eN+.

Доказательство. Докажем первую часть утверждения для Л = в, остальные случаи доказываются аналогично. В силу замечания, сде­ланного в § 2 после предложения 2.1,

_Cl b (fc)^ a (fc)^ c ₂ b (fc)

для всех JceN⁺ и некоторых с_ъ с₂ > 0. Отсюда

fc=i fc=i fc=i

Пример 12.2. Проведем асимптотический анализ следующего ал­горитма, оценивая общее число выполняемых операций в зависимо­сти от исходного значения п:

1:=0;

for i = l to L\/ n ³ + lJ do

k:=i;

while k > 1 do Z:= Z + k; k:= I | I od od

Для внутреннего цикла, выполняемого при начальном значении к, равном значению i, число шагов и общее число операций допуска­ют оценку в (log 0 (можно представить себе, что к записано в тро­ичной системе счисления, тогда каждый шаг удаляет одну циф­ру из записи к). Таким образом, затраты на выполнение внешне­го цикла представляют собой £ а(к), где у(п) = L\/ n ³ + 1J, a (fc) =

fc=i

= 6(logfc), и по предложению 12.1 допускают оценку в(X! \°gk

fc=l

или 6(log(y>(n)!). Так как у(п) -> оо при п -> оо, то можно при­менить соотношение log(y>(n)!) = e(y>(n) log^(n)), которое являет-

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

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

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

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

2 2 i.

i =i

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

c i^l| vi l|^ 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 — ], соот-

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