Лекции о сложности алгоритмов. С. А. Абрамов (1121249), страница 18
Текст из файла (страница 18)
Качество оценокДля дальнейшего будет полезным следующее свойство чисел Фибоначчи: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 > ... > xn ). Замена переменной суммирования даетnXTB (n) =⌈log2 k ⌉.(.)k =1Приведенный выше и дополненный в указании к задаче элементарный выводоценки (.) принадлежит М. Оналбекову; в [, разд. .., упр. ] со ссылкой настатью Я. Микусинского ( г.) приведена оценка, фактически совпадающая с (.),но ее вывод опирается на теорию цепных дробей и не столь элементарен и нагляден.Предположение о том, что TE (a1 ) ∼ logφ a1 , насколько известно автору, не доказанои не опровергнуто ( г.).§ .
Завершимость работы алгоритмаДля получения простой асимптотическойоценки TB (n) воспользуемсяpформулой Стирлинга n! ∼ nn e−n 2πn, или, что то же самое,pn! = nn e−n 2πn(1 + o(1)),которая после логарифмирования принимает видlog2 n! = n log2 n − n log2 e +111log2 n + log2 π + + o(1)222(принято во внимание, что log2 (1 + o(1)) = o(1)). Так как 1 < log2 e << 2, тоn log2 n − 2n < log2 n! < n log2 n − n(.)для всех достаточно больших n; в частности, это означает, чтоlog2 n! = n log2 n + O(n).ИмеемnXk =1⌈log2 k ⌉ =nXlog2 k + O(n) = log2 n! + O(n) = n log2 n + O(n).k =1Отсюда получаем оценкуTB (n) = n log2 n + O(n),(.)из которой следует, в частности, что TB (n) ∼ n log2 n.Таким образом, тщательный анализ суммы (.) не приводит к существенно лучшей, чем (.), оценке, но зато дает асимптотику TB (n).В § будет показано, что из того, что сложность по числу сравнений некоторой сортировки не превосходит n log2 n + cn, где c — некоторая константа, следует, что эта сложность есть n log2 n + O(n).
Изэтого будет следовать, что для сложности по числу сравнений сортировки фон Неймана выполнено TvN (n) = n log2 n + O(n); мы обозначаем эту сортировку буквами vN, от фамилии von Neumann.§ . Завершимость работы алгоритмаЕсли выполнение циклического (итерационного) алгоритма не завершается для некоторого входа v, то сложность этого алгоритма неопределена для значения аргумента, равного kv k.
Поэтому анализсложности алгоритма прямо или косвенно включает исследование завершимости.Установление завершимости может быть рассмотрено и как самостоятельная задача. Когда функция L подбирается для выяснениязависимости числа шагов алгоритма от размера входа задачи, то приГлава . Оценивание числа шагов (итераций) алгоритманаличии выбора более предпочтительной является функция с медленным ростом (имеется в виду рост при увеличении размера входа);даже если при этом усложняется доказательство того, что L обладаетвсеми нужными свойствами, мы зато получаем более точную оценкучисла шагов алгоритма.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
