Лекции о сложности алгоритмов. С. А. Абрамов (1121249), страница 17
Текст из файла (страница 17)
Укажем здесь еще одно егоприменение, касающееся вычислительной геометрии: он позволяетбыстро определять, принадлежит ли произвольная точка 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 — бинарный.
По числу перемещений сложность этой сортировки квадратична, здесь эта сортировка уступаетсортировке фон Неймана. Пространственную сложность сортировкибинарными вставками можно считать равной нулю (все делается натом же месте), а для сортировки фон Неймана эта сложность есть n.Пример .. Число итераций численных алгоритмов тоже частооценивают сравнением размеров данных, соответствующих текущимитерациям, с элементами последовательности, которая может иметь,nнапример, вид q n или q 2 (q < 1), n = 0, 1, ..., и т. д. Этим способомТакую функцию можно назвать функцией Ляпунова цикла, подразумевая аналогиюс функцией, убывающей вдоль решения обыкновенного дифференциального уравнения(аналогия принадлежит С.
С. Лаврову, см. [, разд. ..]). Это не единственная аналогия между дифференциальными уравнениями и циклическими алгоритмами и программами. Например, понятие первого интеграла, или закона сохранения, сопоставимо с понятием инварианта цикла и т. д.§ . Качество оценокполучаются оценки числа итераций для классических методов (алгоритмов) приближенного решения уравнений.
Вспомним две такиеоценки.Пусть корень уравнения f (x) = 0 разыскивается на отрезке [a, b],на котором функция f (x) непрерывна, f (a) f (b) ¶ 0. Ошибка не должна превышать данного ǫ > 0. При ǫ → 0 и фиксированных f (x), a, bчисло итераций метода делений пополам естьlog21+ O(1).ǫ(.)Метод же Ньютона (касательных) требует1O log log(.)ǫитераций при соблюдении ограничений на функцию f (x), обеспечивающих сходимость метода.§ .
Качество оценокПосле вывода оценки сложности алгоритма часто возникает вопросо том, насколько эта оценка хороша и нельзя ли входящие в оценку константы и функции заменить другими так, чтобы оценка сталаболее точной, и, как следствие, несущей больше информации об исследуемом алгоритме.Пример .. В примере . для сложности TE (a1 ) по числу делений алгоритма Евклида мы легко получили верхнюю оценку a1 , а затем, после некоторых усилий, пришли к логарифмической верхнейоценке (.).
Отвлекаясь от значений констант, перейдем от (.) кTE (a1 ) = O(log a1 ).(.)Нами пока не доказано, что оценка (.) pявляется точной, и, какследствие, что не верна, скажем, оценка O( log a1 ) или O(log log a1 )и т. д. Чтобы доказать точность (.), достаточно подобрать для алгоритма Евклида последовательность входов(1)(2)(2)(a(1)0 , a1 ), (a0 , a1 ),a(n)1...таких, что последовательность(последовательность размеров вхо(n)(n)да) неограниченно возрастает и CE (a(n)0 , a1 ) = Ω(log a1 ) при n → ∞;(n)(n)тогда, очевидно, будем иметь TE (a1 ) = Ω(log a1 ).Фактически, нам нужна последовательность таких входов возрастающего размера, для каждого из которых алгоритм Евклида работает медленно. Подойдет, например, последовательность входовГлава .
Оценивание числа шагов (итераций) алгоритма(Fn+1 , Fn ), n = 0, 1, ..., где F0 , F1 , F2 , ... — числа Фибоначчи, определяемые равенствами F0 = 0, F1 = 1 и правилом «каждое следующее число равно сумме двух предыдущих», т. е. рекуррентным соотношениемFn+2 = Fn+1 + Fn . Из определения чисел Фибоначчи следует, что применение алгоритма Евклида к Fn+1 , Fn при n ¾ 1 требует n делений(все частные будут равны единице), поэтому CE (Fn+1 , Fn ) = n.По индукции доказывается, что для всех неотрицательных n справедлива формула Бине:15Fn = p (φ n − (−φ )−n ),гдеφ=(.)p1+ 5= 1,61803...2(деление отрезка в отношении 1 : φ называют золотым сечением).Так как φ > 1, то из (.) получаемp(.)φ n = 5Fn (1 + o(1)),и, поскольку logφ (1 + o(1)) = o(1), с помощью логарифмирования(.) по основанию φ имеемCE (Fn+1 , Fn ) = n = logφ Fn + O(1) = Ω(log Fn ),откуда следует, что оценка (.) точная.Мы докажем более сильное утверждение:TE (a1 ) >1logφ a1 + γ,4(.)где γ — некоторая константа.
Это вместе с (.) дастTE (a1 ) = Θ(log a1 ).(.)Приступая к доказательству, мы перейдем от функции CE (a0 , a1 ),имеющей два аргумента, к функции одного аргумента. Каждому вхоaду (a0 , a1 ), a0 ¾ a1 > 0, мы сопоставим рациональное число r = 0 ¾ 1,a1которое однозначно определяет число шагов алгоритма Евклида дляa0 , a1 . (Пустьa0ã= 0 , ã0 и ã1 взаимно просты, a0 = uã0 , a1 = uã1 ; тоa1ã1гда остатки a2 , a3 , ... и ã2 , ã3 , ..., возникающие в ходе применения алгоритма Евклида к a0 , a1 и соответственно к ã0 , ã1 , отличаются лишьмножителем u.) Будем обозначать это число шагов через CE′ (r). Такимобразом, если r =a0, то CE′ (r) = CE (a0 , a1 ).a1§ .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
