С.А. Абрамов - Лекции о сложности алгоритмов (pdf) (1123764), страница 19

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 19)

Оказывается, что пристабильных неправильных ответах обучаемого на задаваемые вопросы математическое ожидание времени, проходящего до получениявсех, кроме какого-то одного, вопросов с номерами 1, 2, ..., u, естьконечная величина. Докажем конечность среднего времени ожидания какого-нибудь одного вопроса с номером от 1 до u, далее можноприменить индукцию.

Вероятность получить такого рода вопрос после i вопросов с номерами из диапазона от u + 1 до n полностьюопределяется значениями u, m, i:m−u+i−1um−u m−u+1·...·.mm+1m+i−1m+iЭта вероятность при i > u равнаu(m − u)(m − u + 1)...(m − 1).(m − u + i)(m − u + i + 1)...(m + i − 1)(m + i)Поэтому искомое математическое ожидание есть сумма некоторогоконечного числа слагаемых и ряда∞Xi = u +1u(m − u)(m − u + 1)...(m − 1)(i + 1),(m − u + i)(m − u + i + 1)...(m + i − 1)(m + i)илиu(m − u)(m − u + 1)...(m − 1)∞Xi = u +1i+1.(m − u + i)(m − u + i + 1)...(m + i)Упрощая, получаемu(m − u)(m − u + 1)...(m − 1)∞Xj =1j +u+1.( j + m)( j + m + 1)...( j + m + u)§ . Вложенные циклы (дополнительные примеры)Ряд,в это выражение, сходится, так как j-й член ряда есть входящий1Θ u и u ¾ 2.jЭто рассуждение сохраняет силу и в том случае, когда вопросыс номерами 1, 2, ..., u являются одним и тем же вопросом, что позволяет отметить следующую характерную черту алгоритма кратныхкарт:Если изначально все вопросы имеют кратность 1 и обучаемый дает на все вопросы неправильные ответы, то математическое ожидание времени до наступления момента, к которому обучаемый получит хотя бы по одному разу каждый из вопросов, равно бесконечности, хотя вероятность наступления такого момента равна 1.

Еслиже изначально все вопросы имели большие единицы кратности (например, все они имели кратность 2), то обсуждаемое математическое ожидание конечно.§ . Вложенные циклы (дополнительные примеры)При анализе сложности вложенных циклов мы естественно приходимк вычислению и оцениванию кратных сумм.Пример .. Число обменов при транспонировании (n × n)-матрицы (aij )for i = 1 to n − 1 dofor j = i + 1 to n do aij ↔ a ji ododестьnP−1nPi =1 j = i +11=nP−1i =1(n − i) =n2 − n. Аналогично, распознавание сим2метричности данной (n × n)-матрицы требует в худшем случае сравnP−1nnP−1 P(n + 1)(n − 2)(n − i + 1) =1=и т. д.нений в количествеi =1 j = ii =12Легкое получение ответов в примере . объясняется тем, чтов выписанных формальным путем суммах нижние границы суммирования не превосходили верхних; в таких случаях всегда, например,qP1 = q − p + 1.

Но, получая сумму этим формальным путем из опеj=pратора цикла, можно столкнуться с тем, что p > q (оператор циклазатратит 0 шагов), и ответ q − p + 1 будет неправильным. Соответствующий пример дается в задаче .Глава . Оценивание числа шагов (итераций) алгоритмаПодходя к асимптотическим оценкам, отметим один простой, нополезный факт.Предложение .. Пусть Λ — один из символов O, Θ, Ω.

Пустьa(k), b(k) определены для всех k ∈ N+ и принимают положительныезначения (не обязательно целые); пусть a(k) = Λ(b(k)), k → ∞. ТогдаP‹nnPa(k) = Λb(k) , n → ∞. Утверждение остается справедливымk =1k =1и при замене верхней границы суммирования n на ϕ (n) для любойфункции ϕ (n), определенной для всех n ∈ N+ и принимающей значенияв N+ .Доказательство. Докажем первую часть утверждения для Λ = Θ,остальные случаи доказываются аналогично. В силу замечания, сделанного в §  после предложения .,c1 b(k) ¶ a(k) ¶ c2 b(k)для всех k ∈ N+ и некоторых c1 , c2 > 0. Отсюдаc1nXk =1b(k) ¶nXa(k) ¶ c2nXb(k).k =1k =1Пример ..

Проведем асимптотический анализ следующего алгоритма, оценивая общее число выполняемых операций в зависимости от исходного значения n:l := 0;pfor i = 1 to ⌊ n3 + 1⌋ dok := i ;j kwhile k > 1 do l := l + k ; k := k od3odДля внутреннего цикла, выполняемого при начальном значении k,равном значению i, число шагов и общее число операций допускают оценку Θ(log i) (можно представить себе, что k записано в троичной системе счисления, тогда каждый шаг удаляет одну цифру из записи k). Таким образом, затраты на выполнение внешнеϕP(n)pго цикла представляют собойa(k), где ϕ (n) = ⌊ n3 + 1⌋, a(k) =k =1= Θ(log k), и по предложению . допускают оценку ȁϕP(n)‹log kk =1или Θ(log(ϕ (n)!). Так как ϕ (n) → ∞ при n → ∞, то можно применить соотношение log(ϕ (n)!) = Θ(ϕ (n) log ϕ (n)), которое являет-§ .

Нецелые размеры входа и непрерывные оценочные функциися следствиемформулыСтирлинга (см. § ). Это дает нам оценкуpp33Θ(⌊ n + 1⌋ log⌊ n + 1⌋) для интересующих нас затрат. После упрощения получаем Θ(n3/2 log n). В этом примере затраты однозначноопределяются по n, поэтому полученная оценка определяет асимптотику сложности рассматриваемого алгоритма при использовании nв качестве размеравхода. ppОценку O(⌊ n3 + 1⌋ log⌊ n3 + 1⌋) и, тем самым, O(n3/2 log n) можно было бы получить не прибегая к формуле Стирлинга, исходя изтого, что сумма конечного числа неотрицательных слагаемых не превосходит произведения наибольшего слагаемого на число слагаемыхсуммы. Для Θ этот прием не работает, как показывает пример суммыnP2i .i =1§ .

Нецелые размеры входа и непрерывные оценочныефункцииПредложение .. Пусть для некоторого алгоритма A можноуказать входы v0 , v1 , ..., размеры которых ограничены сверху и снизуположительными константами c1 и c2 :c1 ¶ kvi k ¶ c2 ,i = 0, 1, ...,и в то же время затраты C AT (vi ) неограниченно возрастают приi → ∞. Тогда не существует такой непрерывной на отрезке [c1 , c2 ]функции f (x) вещественной переменной, что TA (x) ¶ f (x) для всехзначений x размера входа, принадлежащих отрезку [c1 , c2 ].Доказательство. Очевидно, что TA (kvi k) ¾ C AT (vi ), и поэтому последовательность TA (kvi k), i = 0, 1, ..., не ограничена. В то же время,любая функция f , непрерывная на [c1 , c2 ], ограничена на этом отрезке.Сформулируем еще одно столь же легко доказываемое утверждение (доказательство опускаем).Предложение ..

Пусть A — некоторый алгоритм, и f (x) —функция вещественной переменной, определенная на некотором интервале I. Пусть TA (x) ¶ f (x) всякий раз, когда x ∈ I и значение TA (x)определено. Пусть x0 ∈ I и для любых ǫ > 0, N > 0 найдется такойвход v алгоритма A, что | x0 − kv k| < ǫ и C AT (v) > N. Тогда f (x) разрывна в точке x0 .Глава . Оценивание числа шагов (итераций) алгоритмаПример .. Вновь рассмотрим алгоритм Евклида, используя теaперь в качестве размера входа (a0 , a1 ) рациональное число 0 , котоa1рое, как указывалось в примере ., однозначно определяет соответ′ a0, соотствующее количество делений с остатком (сложность TEa1ветствующая этому размеру, совпадает с затратами: CE (a0 , a1 )).

В силу формулы Бине (.) имеемlimn→∞Fn+1= φ,Fnпри этом CE (Fn+1 , Fn ) = n. Поэтому если функциявещественной пеa0 ременной f (x) такова, что CE (a0 , a1 ) ¶ f, то, в силу предложеa1ния ., f (x) разрывна в точке φ . Мы воспользовались тем, что длялюбого ǫ > 0 и любого натурального N найдется рациональное числоuu/v такое, что |φ − | < ǫ и CE (u, v) ¾ N.vМожно доказать, что здесь дело не в числе φ — то же самое справедливо для любого x0 > 1. Пусть 0 < ǫ < x0 − 1. Докажем, что в рациональных точках ǫ -окрестности Vx0 ,ǫ числа x0 функция TE′ (r) не является ограниченной. Предположим противное: пусть r =u0∈ Vx0 ,ǫ — раu1циональное число, на котором достигается максимум.

Пусть частные,возникающие в процессе применения алгоритма Евклида к u0 , u1 ,равны q1 , q2 , ..., qn :u i −1 = q i u i + u i +1 ,i = 1, 2, ..., n,un+1 = 0.Выберем δ > 0 столь малым, что Vr,δ ⊂ Vx0 ,ǫ , и возьмем любое s ∈ Q \ Zuuтакое, что n−1 − s < δ (легко заметить, что n−1 = qn ∈ Z). Пустьununll, m — такие целые, что s = . Используя q1 , q2 , ..., qn , найдем v0 , v1 , ...m..., vn ∈ N+ , для которыхvi−1 = qi vi + vi+1 ,i = 1, 2, ..., n,и vn−1 = l, vn = m. Индукцией по k легко доказать, что для k = 0, 1, ......, n − 1 vn−k−1 un−k−1 −(.) < δ.vun− kn− kВ самом деле, для k = 0 это очевидно; остается показать, что при0 < k < n − 1 из (.) следует vn−k−2 un−k−2 −(.) < δ.vn−k−1u n− k − 1§ .

Нецелые размеры входа и непрерывные оценочные функцииИмеемqv+vvvn−k−2= n− k − 1 n− k − 1 n− k = q n − k −1 + n− k ,vn−k−1vn−kvn−k−1u n− k − 2qu+ u n− ku= n− k − 1 n− k − 1= q n − k −1 + n− k ,u n− k − 1u n− ku n− k − 1откуда un−k | un−k−1 vn−k − un−k vn−k−1 | vn−k−2 un−k−2 vn−k−−.==vn−k−1u n− k − 1vn−k−1u n− k − 1un−k−1 vn−k−1Неравенство (.) можно переписать в виде| un−k−1 vn−k − un−k vn−k−1 |< δ;un−k vn−kэто неравенство влечет| un−k−1 vn−k − un−k vn−k−1 |< δ,un−k−1 vn−k−1так как un−k−1 vn−k−1 > un−k vn−k .

Неравенство (.) доказано, и индукvvция завершена. Следовательно, 0 ∈ Vs,δ и, тем самым, 0 ∈ Vx0 ,ǫ . Ноvv11v vTE′ 0 > n, так как s = n−1 ∈/ Z. Это противоречит предположениюv1vnu о максимальности значения TE′ 0 .u1В силу предложения . мы получаем следующее:Пусть размер каждого входа (a0 , a1 ) алгоритма Евклида определенкак r = a0 /a1 (рациональное число ¾ 1), и в соответствии с этим рассматривается сложность TE′ (r) этого алгоритма по числу делений.Пусть функция f (x) вещественной переменной, определенная всюдуна бесконечном полуинтервале I = [1, ∞), такова, что TE′ (r) < f (r) привсех рациональных r ¾ 1. Тогда f (x) является разрывной в любой принадлежащей I точке.Нелишне заметить, что при целочисленном размере входа условиепредложения . может выполняться, если только для некоторого целого n, c1 ¶ n ¶ c2 , сложность TA (n) бесконечна.Приводившиеся ранее оценки (.), (.) для числа итераций методов деления пополам и касательных используют, фактически, нецелый размер 1/ǫ .

Положение спасается тем, что при малом изменении ǫ не происходит катастрофического увеличения числа итераций.Эту ситуацию можно было бы считать типичной, а пример . искусственным, если бы упомянутые возможные трудности не приводили бы иногда к реальным ошибкам. В приложении C рассмотренаизвестная алгоритмическая проблема, связанная с алгебраическимиГлава . Оценивание числа шагов (итераций) алгоритмачислами («проблема орбит»), для которой в свое время было предложено и опубликовано неверное решение, и причина ошибки былав том, что авторы проглядели ту негативную возможность, котораяпоказана в примере ..В ситуациях, подобных описанной в примере ., мы не можемиспользовать в оценках вида TA (x) < f (x), TA (x) = O( f (x)), TA (x) == Θ( f (x)) в качестве функции f (x), скажем, логарифм, степеннуюи показательную функции, полиномы и т.

Характеристики

Список файлов лекций