С.А. Абрамов - Лекции о сложности алгоритмов (pdf) (1123764), страница 17
Текст из файла (страница 17)
По числу перемещений сложность этой сортировки квадратична, здесь эта сортировка уступаетсортировке фон Неймана. Пространственную сложность сортировкибинарными вставками можно считать равной нулю (все делается натом же месте), а для сортировки фон Неймана эта сложность есть 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§ . Качество оценокДля дальнейшего будет полезным следующее свойство чисел Фибоначчи:Fn2 − Fn−1 Fn+1 = (−1)n , n = 1, 2, ...(.)(доказывается индукцией по n). Рассмотрим вложенные отрезки Φ1 ⊃⊃ Φ2 ⊃ Φ3 ⊃ ... числовой прямой:ih FF2n, 2n+1 , n = 1, 2, ...Φn =F2n−1F2nСоотношение (.) позволяет установить, что ни один из этих1. Очевидно, чтоотрезков не пуст и что длина отрезка Φn равнаF2n−1 F2nΦ1 = [1, 2] (рис. ). Далее можно доказать, что если рациональноеzzz1F2F1F4F3F6F5Рис. .
Расположение чиселΦ1}|Φ2}|Φ3}|......φ ...{{{2F7F6F5F4F3F2Fn+1и интервалов Φn , n = 1, 2, ...Fna0принадлежит Φn , n > 2, то деление a0 на a1 дает ненулевойa1aостаток a2 , и 1 принадлежит Φn−1 . В самом деле, мы имеемa2число1<F2n+1aF2n¶ 0¶< 2.F2n−1a1F2nСледовательно, частное от деления a0 на a1 с остатком равно 1, т. е.a2 = a0 − a1 . Далее,a0 − a1a= 0 − 1,a1a1поэтомуF2n+2F2na−1¶ 2 ¶− 1.F2n−1a1F2nНоF − F2n−1FF2n− 1 = 2n= 2n− 2 ,F2n−1F2n−1F2n−1Глава . Оценивание числа шагов (итераций) алгоритмаF2n+1FFa− 1 = 2n−1 ; мы имеем, следовательно, 2n−2 ¶ 2 ¶F2nF2nF2n−1a1и, аналогично,¶F2n−1иF2nFF2na¶ 1 ¶ 2n− 1 .F2n−1a2F2n−2Получаемa1∈a2h F2nF2n−1,(.)F2n−1 i h F2n−2 F2n−1 i⊂,= Φ n −1 .F2n−2F2n−3 F2n−2Отрезки Φ2 , Φ3 , ... не содержат целых чисел, поэтому из доказанногоможно заключить, что если r ∈ Φn ∩ Q, n > 2, то CE′ (r) ¾ n.Пусть теперь фиксировано a1 ∈ N+ .
Рассмотрим множествоnoaM = r : r = 0 , a0 = a1 , a1 + 1, ... .a1Точки, соответствующие элементам множества M, расположены на1правой полуоси, начиная с , с шагом ; хотя бы одна из этих точекa1непременно принадлежит отрезку Φn , коль скороотрезка Φn , т. е.1меньше длиныa111¶, или, что то же самое, a1 ¾ F2n−1 F2n . Пустьa1F2n−1 F2nN — самое большое значение n, для которого выполняется это неравенство (такое N существует, так как единственной точкой, принадлежащей бесконечному числу отрезков рассматриваемого семейства,является φ ∈/ Q).
Тогда F2N F2N +1 > a1 . Из формулы Бине следует, что15F2N F2N +1 = φ 4N (1 − (−φ )−4N )(φ − (−φ )−4N −1 ),откудаF2N F2N +1 < cφ 4N ,где c — некоторая положительная константа. Таким образом, cφ 4N >> a1 иN>11logφ a1 − logφ c.4Имеем CE′ (r) ¾ N − 1 > logφ a1 − logφ c − 1 по крайней мере для од4ного рационального числа r ∈ M, откуда следует соотношение (.).Переходя к размеру входа m = λ(a1 ), мы можем воспользоваться теоремой . из § и получить для сложности TE∗ (m) по числу§ .
Качество оценокделений соотношение TE∗ (m) = Θ(m). (В силу теоремы . TE∗ (m) == Ω(log 2m−1 ) = Ω(m) и TE∗ (m) = O(log 2m ) = O(m).)Число шагов расширенного алгоритма Евклида (см. пример .)совпадает с числом шагов обычного алгоритма Евклида. Мы получаем следующее:Если рассматривать a1 как размер входа (a0 , a1 ) расширенногоалгоритма Евклида, то для мультипликативной сложности TEE (a1 )этого алгоритма выполнено TEE (a1 ) = Θ(log a1 ). При рассмотренииm = λ(a1 ) в качестве размера входа a0 , a1 расширенного алгоритма∗Евклида имеем для мультипликативной сложности оценку TEE(m) == Θ(m).
Все это сохраняет силу и для сложности TE∗ (m) «обычного»алгоритма Евклида.Запись алгоритма Евклида в форме (.) далека от записи в виде«приличной» компьютерной программы не только в смысле использованной символики, но, главное, в смысле предписываемого расточительного расхода памяти (использован массив, и при буквальномследовании алгоритму (.) мы бы имели SE (a1 ) = Θ(log a1 )). С точки зрения программирования более приемлемой будет, например,записьa := a 0 ; b := a 1 ;while b > 0 dod := rem(a, b); a := b; b := dod(rem — знак операции нахождения остатка). После выполнения алгоритма имеем a = íîä(a0 , a1 ). Использовано только три дополнительных переменных (a, b и d), и мы получаем SE (a1 ) = 3.Оценку (.) можно усилить, показав, что найдется константа γ′такая, что1(.)TE (a1 ) > logφ a1 + γ′2(см.
задачу ). Часто в литературе оценки снизу для сложности в худшем случае алгоритма Евклида по числу делений выводят из оценки,полученной в г. Г. Хейлбронном для сложности в среднем:¯T¯E (a1 ) = 12 ln 2 ln a1 + O(1).2π(.)Последняя оценка обосновывается весьма непросто. Из (.) выводится, чтоTE (a1 ) >12 ln 2ln a1 + γ′′π2Глава .
Оценивание числа шагов (итераций) алгоритмадля некоторой константы γ′′ . Однако при больших a1 оценка (.)для TE (a1 ) является более строгой (112 ln 2ln φ = 0,40554... < ) и вдо2π2бавок выводится элементарно .Может быть доказано (см. задачу ), что TE (a1 ) < logφ a1 + c, гдеc — некоторая константа (заметим, что logφ 2 = 1,44...
< 2) .Рассуждения, сходные с приведенными при доказательстве неравенства (.), показывают, что для каждого a0 можно подобрать a1 ,a0 ¾ a1 , так, что будет выполнятьсяCE (a0 , a1 ) >1logφ a0 + β ,4(.)где β — некоторая константа. В данном случае можно рассмотретьвложенные отрезки Ψ1 ⊃ Ψ2 ⊃ Ψ3 ⊃ ...:ih FF2n, 2n−1 , n = 1, 2, ...Ψn =F2n+1F2n(при n > 1 отрезок Ψn не содержит чисел видаделится нацело на a1 иэтим в § .1, m ∈ N+ ); если a0 неma1a∈ Ψn , то 2 ∈ Ψn−1 и т. д.
Мы воспользуемсяa0a1Пример .. Сортировка массива длины n бинарными вставками выполняется за n − 1 шаг, причем на l-м шаге число сравнений непревосходит ⌈log2 (l + 1)⌉ и, следовательно, не превосходит ⌈log2 n⌉ налюбом из шагов, — это приводит к оценке (.). Возникает вопрос,не сможем ли мы получить существенно лучшей оценки сверху, расnP−1смотрев сумму⌈log2 (l + 1)⌉, которая совпадает со значением TB (n),l =0т. е. сложности по числу сравнений (такое число сравнений достигается, например, в случае, когда изначально массив имеет обратнуюупорядоченность: x1 > x2 > ...
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
