С.А. Абрамов - Лекции о сложности алгоритмов (pdf) (1123764), страница 16
Текст из файла (страница 16)
Функции, убывающие по ходу выполнения алгоритмаЧтобы это показать, обратимся к (.). Пусть уже известны 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.Бинарный поиск находит широчайшее применение при поиске информации в разнообразных таблицах. Укажем здесь еще одно егоприменение, касающееся вычислительной геометрии: он позволяетбыстро определять, принадлежит ли произвольная точка Q выпуклому n-угольнику, заданному вершинами P1 , P2 , ...
Pn . Можно легкопостроить какую-нибудь внутреннюю точку O данного n-угольника.В силу его выпуклости точка Q — внутренняя, если и только еслиQ и O лежат в одной полуплоскости относительно любой из прямыхP1 P2 , ..., Pn−1 Pn , Pn P1 . Это соображение приводит к имеющему временную сложность Θ(n) алгоритму. Но допустим, что проведены n добавочных лучей (рис.
), исходящих из точки O и проходящих черезP5...P4QOP3P1P2Рис. . Точка Q лежит между двумя лучами, проведенными из внутреннейточки O многоугольника через его вершины.вершины (считаем, что O 6= Q, иначе мы сразу бы заключили, чтоQ принадлежит многоугольнику). Можно установить, какому из углов∠ P1 OP2 , ..., ∠ Pn−1 OPn , ∠ Pn OP1 принадлежит точка Q: если углы прону-Глава . Оценивание числа шагов (итераций) алгоритмамерованы в указанном порядке, то бинарным поиском определяетсяномер m угла, 1 ¶ m ¶ n; при этом если Q лежит на одном из проведенных лучей, то из двух значений m берется любое. Узнав m, мыпроверяем согласованность расположения точек O и Q по отношениюк прямой, являющейся продолжением той стороны многоугольника,концы которой лежат на сторонах m-го угла.Теперь заметим, что в самом проведении лучей OP1 , OP2 , ..., OPnнет необходимости: сравнение ∠ P1 OQ с ∠ P1 OPi требует ограниченного числа операций и в том случае, когда нам лишь известны координаты точек O, Q, P1 , Pi .Основывающийся на бинарном поиске алгоритм распознаванияпринадлежности точки выпуклому n-угольнику имеет сложностьO(log n) по общему числу операций и пространственную сложностьO(1).Полезным для решения ряда задач является то обстоятельство, чтоесли точка не принадлежит данному выпуклому n-угольнику, то с помощью этого алгоритма мы дополнительно определяем одну из сторон n-угольника, которая из этой точки видна целиком (рис.
)....QOРис. . Для точки Q , не принадлежащей данному выпуклому n-угольнику,находим сторону n-угольника, которая из Q видна целиком.Пример .. Установим число этапов слияния при сортировке,предложенной Дж. фон Нейманом (которая является одним из вариантов сортировки слияниями). При сортировке фон Неймана шаг зашагом происходят переброски элементов исходного массива в дополнительный массив и наоборот, и каждая переброска сопровождается слиянием соседних сегментов массива (рис.
). В данном случае в качестве вспомогательного размера массива удобно рассмотреть k — число сегментов (первоначально k = n, затем, шаг за шагом, k довольно быстро убывает). При анализе бинарного поискаместа элемента мы фактически использовали, что если 2m−1 ¶ k < 2m ,§ . Функции, убывающие по ходу выполнения алгоритмаа)б)в)Рис. . Три последовательных шага сортировки фон Неймана, удлиняющихупорядоченные участки (сегменты): а) переход от семи сегментов к четырем; б) переход от четырех сегментов к двум; в) переход от двух сегментовк одному (массив полностью упорядочен).то при k > 1 на следующем шаге мы будем иметь дело с k ′ таким,что k ′ < 2m−1 .
В случае же сортировки фон Неймана ситуация такова,что если на каком-то шаге имеем k > 1 уже построенных сегментови 2m−1 < k ¶ 2m (это соответствует тому, что ⌈log2 k ⌉ = m), то на следующем шаге сегментов будет k ′ < k и 2m−2 < k ′ ¶ 2m−1 (это соответствует тому, что ⌈log2 k ′ ⌉ = m − 1). Поэтому функция L(k) = ⌈log2 k ⌉,где k — текущее число построенных сегментов, убывает с каждымшагом ровно на единицу. Таким образом, число этапов слияния, иличисло перебросок сортируемых элементов из массива в массив, равно⌈log2 n⌉. Это позволяет утверждать следующее:Сложность сортировки фон Неймана по числу сравнений меньше,чем n⌈log2 n⌉; сложность по числу присваиваний равна n⌈log2 n⌉.В самом деле, каждый этап слияния, сопровождаемый переброской элементов из массива в массив, требует n присваиваний.
Числосравнений при каждом слиянии по крайней мере на единицу меньше, чем длина получаемого упорядоченного сегмента: известно, чточисло тех сравнений, которые априори могут потребоваться для слияния двух упорядоченных массивов, содержащих соответственно k и mэлементов, k ¶ m, лежит в диапазоне от k до k + m − 1 (обе указанныеграницы достижимы).Вновь обращаясь к примеру ., мы видим, что, основываясь насортировке фон Неймана, можно получить алгоритм построения выпуклой оболочки данных n точек координатной плоскости, имеющийсложность O(n log n) в худшем случае по общему числу операций.Некоторое различие между примером . и примерами ., . состоит в том, что в примере . мы определяли L как функцию самоговхода алгоритма и из полученной оценки для затрат выводили оценку для сложности (переходили от входа как такового к его размеру),а в ., . мы изначально рассматривали L как функцию размера.Глава .
Оценивание числа шагов (итераций) алгоритмаВ этих двух последних примерах значения функции L возникали изсравнений размера n с элементами некоторой последовательности sk ,k = 0, 1, ... (в обоих случаях было sk = 2k ). В примере . удобно было считать, что L(n) = k, если sk−1 ¶ n < sk , а в примере . — еслиs k −1 < n ¶ s k .Типичный итерационный алгоритм содержит цикл, в котором набор v начальных величин преобразуется в набор v ′ , затем v ′ преобразуется в v ′′ и т. д.
Функция L, которую мы подбираем, должна принимать неотрицательные значения и быть определенной либо на самихнаборах величин, либо на их размерах; в обоих случаях функция должна убывать по ходу выполнения алгоритма:L(v) > L(v ′ ) > L(v ′′ ) > ...в первом случае, илиL(kv k) > L(kv ′ k) > L(kv ′′ k) > ...во втором. Значение L(v) или соответственно L(kv k) дает верхнююграницу для числа шагов цикла. Заметим попутно, что, исходя из установленной в примере .сложности бинарного поиска, мы сразу можем получить верхнююоценкуTB (n) ¶ (n − 1)⌈log2 n⌉(.)для сложности по числу сравнений сортировки бинарными вставками; мы используем для обозначения этой сортировки букву B, отанглийского слова binary — бинарный.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
