С.А. Абрамов - Вычислительная сложность алгоритмов (лекции) (1121252), страница 4
Текст из файла (страница 4)
задачу 24). Используя это равенство, длядлины сегмента Φ n получаем выражение:Φn =F2 n+1 F2 nF F − F22n1−= 2 n+1 2 n−1=F2 n F2 n−1F2 n F2 n−1F2 n F2 n−11811≤ Φn =, а дляa1F2 n F2 n−11=⇔ a1 < F2 N +1F2 N + 2 .F2 N +1 F2 N + 2Так как Φ n → 0 при n → ∞ , a1 > 1 ⇒ ∃N : ∀n ≤ N выполняется1> Φ N +1a1N + 1 неравенство уже не выполняется, т.е.Используем формулу Бене и получим:()()1 2 N +21 2 N +1φ− (−φ ) −2 N −1 ⋅φ− (−φ ) −2 N −2 < cφ 4 N55a1 < F2 N +1 F2 N +2 =1logφ a1 − logφ c , что доказывает оценку TE (a1 ) = Θ(log a1 ) . Для сложности в среднем412 ln 2ln a1 + O(1) .можно получить оценку TE (a1 ) =2⇒N>πРасширенный алгоритм Евклида (EE).Можно показать, что ∃s, t ∈ Z : sa0 + ta1 = НОД(a0 , a1 ) .
В частности, если a0 и a1 взаимнопростые, то ∃s, t ∈ Z : sa0 + ta1 = 1 .Пусть в алгоритме Евклида уже найдены a0 , a1 ,..., ai , 1 ≤ i ≤ n − 1 и пусть найдены s0 , t0 ;s1 ,t1 ; … ; si , ti такие, что s0 a0 + t0 a1 = a0 ; s1a0 + t1a1 = a1 ; … ; si−1a0 + ti−1a1 = ai−1 ; si a0 + ti a1 = ai .ai−1 = qi ai + ai+1 ⇒ ai+1 = ai−1 − qi ai = si−1a0 + ti−1a1 − qi ( si a0 + ti a1 ) = ( si−1 − qi si )a0 + (ti−1 − qi ti )a1 , т.е.1424314243si +1ti +1si+1 = si−1 − qi si ; ti+1 = ti−1 − qi ti , при этом s0 = 1 , t0 = 0 , s1 = 0 , t1 = 1 .Пример. a0 = 39; a1 = 15Остатки, получаемые алгоритмом Евклида: 9, 6, 3, 0.s, t: 1,-2; -1,-3; 2,-5; ⇒ 2 ⋅ 39 + (−5) ⋅15 = 3 = НОД(39,15) .Алгоритм Евклида, в котором дополнительно определяются числа ti , si буден называтьрасширенным алгоритмом Евклида (EE). Не трудно видеть, что для его сложностисправедлива оценка: ё TEE (a1 ) < 6 log 2 a1 + 3 , т.е.
всё утроилось.Можно также найти числа sn+1 , tn+1 : sn+1a0 + tn+1a1 = 0 (для примера, рассмотренного выше,sn+1 = s5 = −5; t5 = 13 ).Для чисел si , ti можно доказать следующий факт: s1 < s2 < ... < sn+1 , t1 < t2 < ... < t n+1 .Кроме того, sn +1 =a1a0, t n+1 =, тогда sk < a1 , tk < a0 , k = 1,2,..., n .НОД(a0 , a1 )НОД(a0 , a1 )Бинарный поиск (BS = binary search).Есть массив x1 ,..., xn , элементы которого упорядочены по возрастанию.
И есть ещё одинэлемент y, для которого нужно найти место в этом массиве такое, что после вставкиэлемента y полученный массив был упорядоченным. Существуют следующие варианты длявставки y:y ≤ x1 ,1x1 < y ≤ x2 ,2x2 < y ≤ x3 , ... xn−1 < y ≤ xn , xn < yn3n+1Задачей алгоритма является выдача числа от 1 до n + 1 , соответствующего вариантуправильного расположения y.19На псевдокоде алгоритм выглядит следующим образом:p:=1; q:=n-1;while p<q do⎢ p + q⎥;⎣ 2 ⎥⎦r:= ⎢odif xr<y then p:=r+1 else q:=r fiНе трудно видеть, что каждый шаг алгоритма переводит рассматриваемую задачу для⎢k ⎥⎢k ⎥массива длины k к задаче для массива длинны ⎢ ⎥ или ⎢ ⎥ − 1 . Введём функцию⎣2⎦⎣2⎦λ (k ) = ν (k ) , тогда на каждом шаге алгоритма λ (k ) будет убывать хотя бы на 1.
Если y ≤ x1 ,то λ (n) = ⎣log 2 n ⎦ + 1 = TBS (n) = ⎡log 2 (n + 1)⎤ .Сортировка бинарными вставками.Рассмотрим алгоритм сортировки массива, основанный на алгоритме бинарного поиска.Алгоритм заключается в следующем: создается новый массив, который формируется изэлементов исходного, каждый новый элемент занимает место, определяемое алгоритмомбинарного поиска. Тем сам на i-м шаге уже имеется упорядоченный массив из i − 1 элемента,в который вставляется i-й элемент исходного массива.n −1nl =0k =1nДля сложности в худшем случае имеем: TB (n) = ∑ ⎡log 2 (l + 1)⎤ = ∑ ⎡log 2 k ⎤ = ∑ log 2 n + O(1) .k =1n −nИз курса математического анализа известна формула Стирлинга: n!= n en∑ logk =122πn (1 + o(1) ) ⇒n = log 2 n!= n log 2 n + O(n) ⇒ TB (n) = n log 2 n + O (n) .Сортировка фон Неймана (vN).Имеется массив x1 ,..., xn , который требуется упорядочить.
Пусть на каком-то шаге алгоритмамассив разбивается на некоторое число упорядоченных сегментов. Тогда на следующемшаге сегменты объединяются парами и элементы внутри новых сегментов упорядочиваются.Далее опять происходит слияние сегментов по два и т.д. Причём для слияния сегментовиспользуется вспомогательный массив такой же длины, что и исходный. Схематичнодействие алгоритма можно изобразить следующим образом:⇒⇒При слиянии сегментов используется информация о том, что каждый из сливаемыхсегментов сам по себе уже упорядочен, поэтому для слияния и одновременногоупорядочивания двух сегментов длины k необходимо менее 2k операций сравнения, т.к.новый сегмент длины 2k формируется в новом массиве (новый сегмент формируетсяпоэлементно из меньшего из наименьших нерассмотренных элементов исходных сегментов).На первом шаге исходный массив делится на сегменты длины 2 (за исключением, бытьможет, одного сегмента длины 1 в случае, если исходный массив имеет нечётное количествоэлементов), на втором шаге — длины 4 (если не было парного какому-то сегменту, то ещё неболее одного сегмента длины 1, 2 или 3) и т.д.
Таким образом, число этапов (перебросок) всортировке фон Неймана будет равно ⎡log 2 n⎤ . Т.к. число присваиваний на каждом этапе20равно n, то общее число присваиваний, необходимых алгоритму, будет равно n ⎡log 2 n ⎤ . Длячисла сравнений получаем следующую оценку: TvN (n) < n ⎡log 2 n⎤ .Завершимость алгоритмов.Рассмотрим следующий пример.Пример. (блуждание частицы по целым числам) В начале координат имеется частица,которая может двигаться на единицу влево или вправо с одинаковой вероятностью.Оказывается, что ∀m ∈ Z частица рано или поздно попадёт в точку m , причём свероятностью 1. Но среднее необходимое для этого время (даже если m = 1 ) равно ∞ .Алгоритм кратных карт.Имеется колода карточек, на каждой из которых с одной стороны пишутся вопросы, с другой— ответы. Все вопросы разной сложности. Обучаемый перебирая по очереди все карточкидолжен отвечать на вопросы, если ответ неверный, то можно посмотреть ответ на обороте.Если обучаемый отвечает на вопрос карточки, то она изымается, если не отвечает, токарточка возвращается в колоду, плюс добавляется еще одна такая же.Рассмотрим стратегию «двоечника», когда обучаемый всегда отвечает неправильно.Пусть все вопросы в колоде имеют кратность > 1 кроме одной.
Если m — суммарнаякратность карт, то вероятность вытащить первый вопрос (вопрос кратности 1) на первом1шаге равна. Вероятность вытащить первый вопрос на i-м шаге равна:mm −1 mm+i−2 1m −1⋅⋅ ... ⋅⋅=m m +1m + i − 1 m + i (m + i − 1)(m + i )Тогда вероятность того, что рано или поздно вытащат первый вопрос, будет равна:P=∞11+ (m − 1)∑mi =1 ( m + i − 1)( m + i )Покажем, что полученный ряд сходится:n1111111→∞=−⇒ Sn = ∑= −⎯n⎯⎯→m m+nm(m + i − 1)(m + i ) m + i − 1 m + ii =1 ( m + i − 1)( m + i )⇒P=11+ (m − 1) = 1mmЧто соответствует тому, что первый вопрос рано или поздно будет вытащен с вероятностью1. Посмотрим, какое время для этого потребуется:∞T = (m − 1)∑i =1i(m + i − 1)(m + i )Не трудно видеть, что полученный ряд расходится. Это соответствует тому, что длявытаскивания первого вопроса потребуется бесконечное время.Пусть теперь u ≥ 2 карточки имеют кратность 1.
Тогда для вытаскивания вопроса скратностью 1 потребуется времени∞T =∑i =1i + u +1(i + m)(i + m + 1)...(i + m + u )Полученный ряд, как не трудно видеть, сходится, а значит, мы увидим вопрос с кратностью1. Далее по индукции легко установить, что пока u ≠ 1 мы увидим все вопросы.21Допустим, что программа содержит какие-то цифры и её нужно исследовать на сложность.Рассмотрим пример.Пример. Транспонирование матрицы:for i=1 to n-1 dofor j=i+1 to n do aij ↔ aji ododn2 − nЕсли хотим посчитать число обменов, то оно равно ∑ ∑1 = ∑ (n − i ) = ∑ i =.2i =1 j =i +1i =1i =1n −1n −1nn −1Рассмотрим ещё один алгоритм:l:=0;(n)64ϕ7483for i=1 ton + 1 dok:=i;⎣⎦⎢k ⎥while k>1 do l:=l+k; k:= ⎢ ⎥ od⎣3⎦odТребуется оценить сложность приведённого алгоритма.Очевидно, что внутренний цикл while можно оценить через Θ(log i) , т.к.
количество егоитераций совпадает с log 3 i . Поэтому для сложности алгоритма в целом справедлива оценка:⎛ ϕ (n)⎞T (n) = Θ⎜⎜ ∑ log i ⎟⎟ = Θ(log ϕ (n)!) = Θ(ϕ (n) log ϕ (n) ) и с учётом ϕ (n) =⎝ i=1⎠T ( n) = Θ(⎣ n + 1⎦log3)(⎣ n + 1⎦ получаем:3)n3 + 1 = Θ n3 2 log n .До сих пор в качестве размера входа мы использовали целые числа, но определение размеравхода, вообще говоря, допускает использование и рациональных, и иррациональных чисел.a0.
Ранееa1было получено, что TE (n) = Θ(log a1 ) . Рассмотрим следующую последовательность размеровFвхода: rn = n+1 , где Fi — числа Фибоначчи. Из формулы Бене следует, чтоFnПример. В алгоритме Евклида в качестве входа возьмём рациональное число r =1+ 5Fn+1, при этом сложность с ростом n становится всё больше и больше. Если и→φ =Fn2удастся установить оценку TE′ (r ) < f (r ) , то, очевидно, что f (r ) будет разрывная.
Более того,если берём интервал (a, b) , то для любого наперёд заданного N , найдётся рациональноеaчисло r такое, что r = 0 и алгоритму Евклида для чисел (a0 , a1 ) потребуется N шагов.a1Для целых размеров входа таких фокусов нет.Следует отметить, что существуют алгоритмы, для которых целесообразно выбрать вкачестве размера входа нецелое число. Например, алгоритм поиска решения уравнения наотрезке методом деления пополам. Для поиска решения с точностью ε потребуется22log 21ε+ O(1) операций, и в качестве размера входа здесь целесообразно взять величину1⎞⎛Для метода касательных сложность составит O⎜ log log ⎟ .ε⎠⎝231ε.Нижняя граница сложности алгоритмов некоторых классов.Оптимальные алгоритмыПример.
Рассмотрим задачу поиска максимального элемента массива. Очевидно, что решитьэту задачу менее чем за (n − 1) сравнение нельзя.Определение. Пусть A — класс алгоритмов, решающих некоторую задачу. n — размервхода. Функция f (n) называется нижней границей сложности принадлежащих Aалгоритмов, если ∀A ∈ A ⇒ TA (n) ≥ f (n) ∀n .Если сложность зависит от нескольких параметров размеров входа n1 ,..., nk , то нижняяграница — функция нескольких переменных.Для рассмотренного выше примера (поиск максимума) f (n) = n − 1 .Какой именно класс A в определении нижней границы имеет большое значение.
Например,если имеется функция поиска максимума и сложность алгоритма измеряется в обращениях кэтой функции, то и нижняя граница будет иной.Рассмотрим алгоритмы сортировки. Такие алгоритмы можно изобразить в виде дерева:n = 2:1x1 < x2x1 , x20x2 , x1n = 3:x1 < x21x1 , x2 , x3x2 < x31x1 , x3 , x21000x1 < x3x2 , x1 , x30x3 , x1 , x2x3 < x11x3 , x2 , x11x3 < x20x2 , x3 , x1Если высота двоичного дерева h , то число листьев на нём ≤ 2 h (т.к.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
