Лекции о сложности алгоритмов. С. А. Абрамов (1121249), страница 16
Текст из файла (страница 16)
d =2б) Для произвольного простого p вычислить вероятность ψ(p) то+го, что по крайней мереQ одно из случайных x, y ∈ N не делится на p.Из равенства P =ψ(p) определить P.p — простоеУказания. а) ϕ (d) =1P; б) ψ(p) = 1 − 2 .d2pДля того чтобы сделать доказательство «настоящим», надо для произвольного n ∈ N+ детально рассмотреть ситуацию 1 ¶ x, y ¶ n и перейти к пределупри n → ∞, что потребует более кропотливой работы.
См. [, разд. ..].См. [, гл. I, разд. , прим. .].См. [, разд. .., упр. ].Глава Оценивание числа шагов (итераций)алгоритма§ . Функции, убывающие по ходу выполнения алгоритмаЧасто выполнение алгоритма является последовательностью однотипных шагов (итераций). Если все шаги равнозатратны по времени, тообщее их число с точностью до постоянного множителя эквивалентновременным затратам рассматриваемого алгоритма для данного входа, и важной задачей является определение или хотя бы оцениваниечисла этих шагов.Пример ..
Пусть a0 , a1 — натуральные числа, a0 ¾ a1 . Поиск наибольшего общего делителя (íîä) чисел a0 , a1 по алгоритму Евклидатребует выполнения серии однотипных шагов, каждый из которых —деление с остатком:a0 = q1 a1 + a2 ,a1 = q2 a2 + a3 ,...................a n −3 = q n −2 a n −2 + a n −1 ,a n −2 = q n −1 a n −1 + a n ,(.)a n −1 = q n a n .В этом случае an = íîä(a0 , a1 ), так какíîä(a0 , a1 ) = íîä(a1 , a2 ) = ... = íîä(an , 0) = an .Последовательность получаемых остатков убывает (остаток меньшеделителя), при этом все остатки — неотрицательные целые. Не существует убывающей бесконечной последовательности, элементамикоторой являются неотрицательные целые числа, поэтому выполнение алгоритма Евклида (будем обозначать его буквой E) завершаетсядля любых натуральных a0 , a1 , и число делений с остатком не пре-§ .
Функции, убывающие по ходу выполнения алгоритмавосходит a1 . Обозначив через CE (a0 , a1 ) исследуемое число деленийс остатком, получаемCE (a0 , a1 ) ¶ a1(.)(для упрощения записи мы пишем CE (a0 , a1 ) вместо CET (a0 , a1 )). Этоговорит о том, что если a1 рассматривается как размер входа или если a0 , a1 рассматриваются как два параметра размера входа, то сложность алгоритма Евклида по числу делений не превосходит a1 .
Какмы увидим, эта оценка является весьма грубой, но, привлекая сходные рассуждения, можно получать и более тонкие оценки.Формализуем те соображения, которые привели нас к этой первойоценке. Каждый шаг алгоритма имеет дело с парой неотрицательных целых (ai−1 , ai ) и при условии ai 6= 0 перерабатывает эту парув (ai , ai+1 ), где ai+1 равно остатку от деления ai−1 на ai . На множестве пар неотрицательных целых чисел k, l мы определяем функциюL(k, l), принимающую неотрицательные целые значения. Эта функция такова, что когда при выполнении алгоритма Евклида мы переходим от пары (ai−1 , ai ) к паре (ai , ai+1 ), значения функции убывают: L(ai−1 , ai ) > L(ai , ai+1 ).
Так как функция целочисленна, то ее значение убывает с каждым шагом по крайней мере на единицу. Отсюда следует, что общее число шагов не превзойдет значения функции L на исходной паре чисел. Мы рассмотрели функцию L(k, l) = l,и это привело нас к выводу, что число шагов не превзойдет значенияL(a0 , a1 ) = a1 .Для обоснования того, что число делений в алгоритме Евклидарастет медленнее, чем a1 , было бы достаточно найти соответствующую функцию L(k, l), значения которой при больших k, l оказываются существенно меньшими, чем l. Эта функция по-прежнему должнабыть определена для любых неотрицательных целых k, l, k ¾ l, принимать неотрицательные целые значения и убывать при замене парыk, l парой l, r, где r — остаток от деления k на l. Хотя бы одна пара целых неотрицательных k, l, k ¾ l, должна обращать L(k, l) в нуль,иначе вместо L(k, l) можно взять функцию L′ (k, l) = L(k, l) − 1 и т.
д.Предложение .. Пусть k, l ∈ N+ , k > l, и пусть r — остаток отделения k на l. Тогда(i) λ(k) > λ(r), где, как обычно, λ(·) — битовая длина данногочисла;(ii) функцияL(k, l) = λ(k) + λ(l) − 2(.)такова, что L(k, l) > L(l, r).Глава . Оценивание числа шагов (итераций) алгоритмаДоказательство. (i) Имеем k = ql + r, q ¾ 1, откуда k ¾ l + r > 2r.Следовательно, λ(k) > λ(r).(ii) Из λ(k) > λ(r) следует λ(k) + λ(l) − 2 > λ(l) + λ(r) − 2.Очевидно, что функция (.) неотрицательна.
Таким образом,справедлива оценкаCE (a0 , a1 ) ¶ λ(a0 ) + λ(a1 ) − 2.(.)Но если a0 очень велико в сравнении с a1 , то λ(a0 ) + λ(a1 ) − 2 > a1 .Тем не менее, теперь для CE (a0 , a1 ) уже легко выводится хорошаяоценка. Пусть число делений с остатком больше 1. ИмеемCE (a0 , a1 ) = CE (a1 , a2 ) + 1 ¶ λ(a1 ) + λ(a2 ) − 1 ¶ 2λ(a1 ) − 1.ОценкаCE (a0 , a1 ) ¶ 2λ(a1 ) − 1,(.)очевидно, верна и в случае единственного деления: CE (a0 , a1 ) = 1 притом, что λ(a1 ) ¾ 1.Если взять a1 за размер входа (a0 , a1 ), то для сложности по числуделений будем иметьTE (a1 ) = max CE (a0 , a1 ) ¶ 2λ(a1 ) − 1 = 2⌊log2 a1 ⌋ + 2 − 1 ¶ 2 log2 a1 + 1.a0 ¾ a1Доказанное нами можно переформулировать так:Если рассматривать a1 как размер входа a0 , a1 алгоритма Евклида, то для сложности TE (a1 ) по числу делений выполнено неравенствоTE (a1 ) ¶ 2 log2 a1 + 1.(.)Эта же оценка имеет место и при рассмотрении двух параметровa0 , a1 размера входа.Для достаточно больших a1 верхняя оценка (.) существенно лучше, чем TE (a1 ) ¶ a1 .
(Несколько более точная, чем (.), оценка даетсяв задаче .)Рассматривая далее оценки сложности по числу делений алгоритма Евклида, мы будем использовать значение a1 в качестве размеравхода (значение a0 может быть очень большим в сравнении с a1 , нопервое же деление с остатком приведет к a1 , a2 , где a2 < a1 ).Известно, что алгоритм Евклида допускает разнообразные обобщения и расширения. Прежде всего, вместе с íîä(a0 , a1 ) можно находить целые s, t такие, чтоsa0 + ta1 = íîä(a0 , a1 ).(.)§ .
Функции, убывающие по ходу выполнения алгоритмаЧтобы это показать, обратимся к (.). Пусть уже известны a0 , a1 , ......, ai , 1 ¶ i ¶ n − 1, и пусть для них найдены множители s0 , t0 ; s1 , t1 ; ......; si , ti такие, чтоs0 a0 + t0 a1 = a0 , s1 a0 + t1 a1 = a1 , ..., si−1 a0 + ti−1 a1 = ai−1 , si a0 + ti a1 = ai .После выполнения очередного деления с остатком ai−1 = qi ai + ai+1имеем ai+1 = ai−1 − qi ai и(si−1 − qi si )a0 + (ti−1 − qi ti )a1 = ai+1 .Можем положитьs i +1 = s i −1 − q i s i ,t i +1 = t i −1 − q i t i ,i = 1, ..., n − 1;(.)при этомs0 = 1,t0 = 0;s1 = 0,t1 = 1.(.)Решение поставленной задачи дают числаs = sn ,t = tn .В процессе применения этого алгоритма к числам a0 = 39, a1 = 15возникают остатки 9, 6, 3, 0 и соответствующие ненулевым остаткампары множителей суть 1, −2; −1, 3; 2, −5. Имеем 2 · 39 + (−5) · 15 = 3 == íîä(39, 15).Этот алгоритм мы назовем расширенным алгоритмом Евклидаи будем его обозначать буквами EE, от его английского названияextended Euclidean — расширенный евклидов.
Каждый шаг расширенного алгоритма Евклида содержит три мультипликативных операции — одно деление с остатком и два умножения.Если рассматривать a1 как размер входа a0 , a1 расширенного алгоритма Евклида, то для мультипликативной сложности TEE (a1 ) этогоалгоритма имеем TEE (a1 ) ¶ 6 log2 a1 + 3.Расширенный алгоритм Евклида дает возможность решать в целых числах линейные уравнения с целыми коэффициентами (см. задачу ), он также играет существенную роль в модулярной арифметике (см. § ).Если дополнить расширенный алгоритм Евклида еще одним шагом, то получатся sn+1 , tn+1 такие, чтоsn+1 a0 + tn+1 a1 = 0.(.)Например, для a0 = 39, a1 = 15 имеем s5 = −5, t5 = 13.
Легко доказать,что| s1 | ¶ | s2 | ¶ | s3 |, | t1 | ¶ | t2 | < | t3 |,(.)Глава . Оценивание числа шагов (итераций) алгоритмаи при n > 2| s3 | < | s4 | < ... < | sn+1 |,| t3 | < | t4 | < ... < | tn+1 |.(.)Несколько труднее, но также возможно доказать, что | si | и | ti | взаимно просты при i = 1, 2, ..., n + 1 (см. задачу ).
Из (.) и взаимнойпростоты sn+1 и tn+1 следует| s n +1 | =a1,íîä(a0 , a1 )| t n +1 | =a0.íîä(a0 , a1 )Вместе с (.), (.) это дает нам| s n | ¶ a1 ,| t n | < a0 .(.)Эти неравенства пригодятся нам в дальнейшем.Пример .. Бинарный поиск места (т. е. значения p, 1 ¶ p ¶¶ n + 1, — как объяснено в приложении A) элемента y в упорядоченном массиве из n элементов x1 < x2 < ... < xn :p := 1; q := n + 1;while pj < q dokp+q; if xr < y then p := r + 1 else q := r fir :=2odОбозначим этот алгоритм буквами BS от его английского названияbinary search — бинарный поиск. Будем считать число элементов сегмента массива длиной этого сегмента (при рассмотрении задач сортировки и поиска мы называем сегментом массива любую упорядоченную часть x s < x s+1 < ... < xt −1 < xt данного массива).
Легкоj видеть,kkчто от сегмента длины k мы переходим к сегменту длиныили2j kk− 1. Это говорит о том, что с каждым шагом алгоритма функция2L(k) = λ(k), где положительное k является длиной сегмента, рассматриваемого на данном шаге, убывает по крайней мере на единицу,пока не приходим к сегменту, содержащему один элемент, после чего еще одно сравнение полностью решает задачу. Отсюда сложностьбинарного поиска не превосходит λ(n) = ⌊log2 n⌋ + 1. Мы видим также, что если y меньше минимального элемента рассматриваемогосегментаj kдлины k > 1, то длина сегмента на следующем шаге будетkравна. Поэтому если изначально y < x1 , то в ходе бинарного по2иска будут рассматриваться сегменты длиныjnkj kn2n,,, ..., 122§ .
Функции, убывающие по ходу выполнения алгоритмасоответственно (битовая длина каждого следующего элемента последовательности на единицу меньше битовой длины предыдущего), ив целом потребуется в точности λ(n) = ⌊log2 n⌋ + 1 сравнений. Используя утверждение, содержащееся в задаче , мы можем сформулировать установленное свойство бинарного поиска так:Сложность TBS (n) бинарного поиска места элемента в массиве длины n по числу сравнений равна ⌊log2 n⌋ + 1, или, что то же самое,⌈log2 (n + 1)⌉.Выражение ⌈log2 (n + 1)⌉ для указанной сложности иногда бываетудобнее, чем ⌊log2 n⌋ + 1, потому что оно имеет смысл и в вырожденном случае n = 0.Бинарный поиск находит широчайшее применение при поиске информации в разнообразных таблицах.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
