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

95

Ряд, входящий в это выражение, сходится, так как 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 определенной для всех neN+ и принимающей значения

eN+.

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

_Clb(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)), которое являет-