С.А. Абрамов - Вычислительная сложность алгоритмов (лекции) (1121252), страница 13
Текст из файла (страница 13)
+ n) = n(n + 1) = O(n ) , в связи с чем, данный алгоритм не подходит.Предыдущий алгоритм базировался на арифметической прогрессии, что и далоквадратичную сложность. Попробуем оценить сложность подобного алгоритма,базирующегося на геометрической прогрессии. Пусть по прежнему на первой итерациисовершается по одному шагу в одну и другую сторону, тем самым первый членпрогрессии будет равен 1. Выберем произвольное q ∈ N, q > 1 и на каждой k-йитерации будем совершать q k −1 шагов в обе стороны. Исходя из этих данных,получаем, что количество требуемых алгоритму итераций не превзойдёт log q n + 1 ,57тогда суммарное количество шагов не превзойдёт 2 ⋅qlog q n +1−1qn − 1= 2⋅= O(n) , что иq −1q −1требовалось.6.
Доказать асимптотику сложности алгоритма пробных делений (TD), приняв за размер⎛ m2 ⎞*входа битовую длину n: TTD (m = ν (n) ) = Θ⎜⎜ 2 ⎟⎟ .⎝ ⎠Решение. При фиксированной длине числа n, равной m, получаем ограничение назначения n: 2 m−1 ≤ n < 2 m . Согласно постулату Бертрана, в интервале (2 m−1 , 2 m ) найдётсяпростое число n, для определения простоты которого алгоритму пробных делений*( m) :потребуется в точности n − 1 делений.
Следовательно, получаем оценки на TTD⎣ 2 ⎦− 1 < Tm−1*TD⎣ ⎦( m) <⎣ 2 ⎦− 1m*2m−1 − 2 < TTD( m) < 2 m − 1⇔⇔mm⎛ m⎞1**⋅ 2 2 − 2 < TTD(m) < 2 2 − 1 ⇒ TTD(m) = Θ⎜⎜ 2 2 ⎟⎟ .2⎝ ⎠7.f (n) = am n m + ... + a1n + a0 , am ≠ 0 . Доказать утверждения:1)f (n) = O(n k ) ⇔ k ≥ m ;2)f (n) = Ω(n k ) ⇔ k ≤ m ;3)f (n) = Θ(n k ) ⇔ k = m .Решение.a.f (n) = O(n k ) ⇔ ∃C > 0 : f (n) ≤ Cn k ⇔ ∃0 ≤ limb.1nkf (n) = Ω n ⇔ ∃C > 0 : f (n) ≥ Cn ⇔ ∃0 ≤ lim≤ ⇔ k ≤m.n → ∞ f ( n)Cc.f (n) = Θ(n k ) ⇔ ∃c1 , c2 > 0 : c1n k ≤ f (n) ≤ c2 n k ⇔ ∃c1 ≤ limn→∞( )kf ( n)≤ C ⇔ k ≥ m.nkkn→∞f ( n)≤ c2 ⇔ k = m .nk8. Аддитивной цепочкой называется последовательность вида n1 < n2 < ...
< nk , для которойвыполнены два условия: 1) n1 = 1 ; nk = n и 2) ∀i : 1 < i ≤ k ∃s, t : 1 ≤ t ≤ s < i такие, чтоnt + ns = ni . Через l (n) обозначим минимальную длину аддитивной цепочки.Доказать: l (ab) ≤ l (a ) + l (b) − 1, a, b ∈ N .Решение. Рассмотрим минимальную аддитивную цепочку, последним элементомкоторой является a: 1 = n1′ < ... < nl′( a ) = a . Минимальная аддитивная цепочка для b всвою очередь выглядит следующим образом: 1 = n1′′ < ... < nl′′(b ) = b .
Помножим каждыйэлемент цепочки для b на a и получим ещё одну цепочку, которая, вообще говоря, неявляется аддитивной: a = n1′′′< ... < nl′′(′b ) = ab . Не трудно видеть, что последний элементцепочки {n′} равен первому элементу цепочки {n′′′} , т.е. nl′( a ) = n1′′′ . Составим из первойитретьейцепочекодну,объединивихпоравномуэлементу:l (b )6444744481 = n1′ < ... < nl′( a ) = n1′′′< ... < nl′′(′b ) = ab . Не трудно видеть, что так составленная1442443l (a)58последовательность является аддитивной цепочкой, но не обязательно являетсяминимальной.
Откуда следует, что l (ab) ≤ l (a) + l (b) − 1 .9. Дан некоторый отрезок и число n > 1 . Требуется привести алгоритм построения отрезка1от данного со сложностью O(log n) .nРешение. Пусть дан отрезок AB. Для деления отрезка на n воспользуемся теоремойФалеса. Для этого из одного конца данного отрезка выпустим луч и отложим на нём nраз отрезок произвольной длины (пробный отрезок). Получим набор точек A1 , A2 , ..., An .После чего проведём прямую, параллельную An B , через точку A2 , тогда, согласнотеореме, она отсечёт на отрезке AB требуемый отрезок.AnAn−1...A2A1BA1ABnЕсли откладывать пробный отрезок по одному n раз, то сложность такого алгоритмабудет порядка n, и он нам не подойдёт.
Чтобы добиться логарифмической сложностиследует поступить следующим образом: после отложения 2-х пробных отрезков сразунаходим A4 , отложив от A2 отрезок AA2 . Затем сразу можно найти A8 , отложив двараза отрезок AA4 и т.д. по степеням двойки. Отсюда получаем логарифмическуюсложность, и оценка O(log n) будет верна.1 nдоказать, что сложность в среднем3 ln nне является полиномиальной.10. Используя оценку функции Эйлера π (n) >алгоритма пробных делений TTD11. Найти сложность в среднем по количеству обменов для алгоритма сортировки выбором,исключая обмены вида xk ↔ xk .12. Дан массив x1 ,..., xn .
Алгоритм нахождения минимального элемента выглядитследующим образом:m:=x1;for i=2 to n doif xi<m then m:=xi fiodНайти сложность в среднем по числу присваиваний.Решение. Разложим Π n следующим образом:Π n = An1 + ... + Ann ,59где событие Ani заключается в том, что минимальный элемент массива располагается на(n − 1)! 1i-м месте. Не трудно видеть, что Pn ( Ani ) == .
Введём случайную величину ξ n ,n!nn()показывающую затраты алгоритма, тогда T (n) = Eξ n = ∑ E ξ n Ani Pn ( Ani ) . Если событиеi =1Ani имеет место, то ξ n при этом принимает значение ξ n = iT ( n ) = Eξ n =⇒()E ξ n Ani = i⇒1 nn +1i=.∑2n i=113. Имеются кости домино, которые можно класть либо рядом, либо строить навес:...lКакой максимальной длины можно построить навес?14. Дан массив. Описать алгоритм нахождения m-го минимального алгоритма сиспользованием операции разбиения и исследовать его сложность.15.
Доказать, что количество пар (i, j ) , попадающих в стек в алгоритме быстрой сортировки(отложенные задачи), меньше длины начального массива n .16. Доказать, что если считать сложность рандомизированного алгоритма быстройсортировки в количестве обращений к генератору случайных чисел, то она равна Θ(n) .Решение. Если воспользоваться формулировкой алгоритма быстрой сортировки сразрезальщиком, то за каждое разрезание он будет брать ровно 1 рубль, и для1 n2 n−1сложности в среднем получаем: TQS′ (n) = Eχ n = 1 + ∑ (Eχ i−1 + Eχ n−i ) = 1 + ∑ χ k .n i=1n k =0Обозначим TQS′ (n) = Eχ n = f (n) , тогда получим:f ( n) = 1 +2 n−1∑ f (k )n k =0n −1nf (n) = n + 2∑ f (k ) ⇒k =0n−2(n − 1) f (n − 1) = n − 1 + 2∑ f (k )k =0Вычитаем из первого второе и получим: nf (n) − (n + 1) f (n − 1) = 1 ⇔f ( x)f (n) f (n − 1)1, тогда предыдущее выражение−=.
Введём функцию ϕ ( x) =n +1nn(n + 1)1+ x1, ϕ (0) = 0 ⇒перепишется в виде: ϕ (n) − ϕ (n − 1) =n(n + 1)nn1 ⎞11 ⎞1⎛⎛1ϕ ( n) = ∑, откуда f (n) = (1 + n)⎜1 −= ∑⎜ −⎟ = n = Θ( n ) .⎟ =1−k +1⎠n +1⎝ n +1⎠k =1 k ( k + 1)k =1 ⎝ k17. Как реализовать генератор случайных чисел (ГСЧ), чтобы вероятность выпадения числа0 ≤ k ≤ N − 1 была α k (на базе стандартного ГСЧ выдающего числа из (0,1) сравномерным распределением).60Решение. Так как выпадение чисел от 0 до N − 1 является полной группой событий, тоN −1∑αk =0k= 1 .
Пусть стандартный ГСЧ выдаёт число r , тогда если r ∈ (0, α 0 ] , тоn⎛ n−1⎤конструируемый генератор выдает 0, если r ∈ ⎜ ∑ α k , ∑ α k ⎥ , то конструируемыйk =0⎝ k =0⎦генератор выдает n.18. Генератор случайных чисел выдаёт 0 с вероятностью p и 1 с вероятностью 1 − p , где p —1неизвестно. Сконструировать такой ГСЧ, чтобы 0 и 1 выпадали с вероятностьюна2базе первого.19. Во второй формулировке алгоритма быстрой сортировки разрезальщик берёт 1) n рублей,2) n 2 рублей. Найти сложность в среднем.Решение.1) аналогично задаче 16 введём обозначения: f (n) = Eχ n = T (n) , тогдаf ( n) = n +Вычитаемn −1n−22 n−12f (k ) ⇒ nf (n) = n 2 + 2∑ f (k ) ⇒ (n − 1) f (n − 1) = (n − 1) + 2∑ f (k )∑n k =0k =0k =0последнееравенствоипредпоследнегоиполучаем:f (n) f (n − 1)2n − 1nf (n) − (n + 1) f (n − 1) = 2n − 1 ⇒−, введя функцию=n +1nn(n + 1)nf (k )2n − 12k − 1ϕ (k ) =получим ϕ (n) − ϕ (n − 1) =, ϕ (0) = 0 ⇒ ϕ (n) = ∑.n(n + 1)1+ kk =1 k ( k + 1)n1Используя факт из математического анализа ∑ = ln n + O(1) , получаем:i =1 iϕ (n) = 2 ln n + O(1) ⇒ T (n) = f (n) = (1 + n)ϕ (n) = 2n ln n + O(n) .2) аналогично пункту 1 получаем:n −1n−22 n−13f (n) = n 2 + ∑ f (k ) ⇒ nf (n) = n3 + 2∑ f (k ) ⇒ (n − 1) f (n − 1) = (n − 1) + 2∑ f (k )n k =0k =0k =03k 2 − 3k + 1= 3n − 6 ln n + O(1)k (k + 1)k =1n⇒ nf (n) − (n + 1) f (n − 1) = 3n 2 − 3n + 1 ⇒ ϕ (n) = ∑⇒ T (n) = f (n) = (1 + n)ϕ (n) = 3n 2 − 6n ln n + O(n)⎛a a ⎞20.
Бинарный алгоритм Евклида: если a0 и a1 чётные, то НОД(a0 , a1 ) = 2 ⋅ НОД⎜ 0 , 1 ⎟ ;⎝2 2⎠⎛a⎞если a0 — чётное, a1 — нечётное, то НОД(a0 , a1 ) = НОД⎜ 0 , a1 ⎟ ; если оба нечётные, то⎝2⎠максимальное заменяем разностью. Когда одно из чисел станет нулём, тогда второе —НОД . Доказать, что завершается и для количества шагов верна оценка O(log a1 ) .21. При применении алгоритма Евклида к числам a0 > a1 возникают остатки a2 , a3 ,..., an ,an+1 = 0 . Доказать, что a n −t ≥ Ft +1 , t = 0, 1, ... , n − 1 (теорема Ламе).22.
Из условий предыдущей задачи вывести оценку для числа шагов алгоритма Евклида:n < logφ a1 + c .6123. m = ν (a1 ) . Показать, что для числа шагов алгоритма Евклида справедливы оценки:TE (m) ≤ 2m − 1 и TEE (m) ≤ 6m + 3 .Решение. Ранее была получена оценка для сложности алгоритма Евклида в следующемвиде: TE (a1 ) = max C E (a0 , a1 ) ≤ 2ν (a1 ) − 1 = 2 ⎣log 2 a1 ⎦ + 1 (см. стр.
18), что в точностиa0 ≥a1соответствует тому, что TE (m) ≤ 2m − 1 . Для доказательства TEE (m) ≤ 6m + 3 используемполученную ранее оценку TEE (a1 ) < 6 log 2 a1 + 3 (см. стр. 19), и очевидный фактlog 2 a1 < m = ν (a1 ) = ⎣log 2 a1 ⎦ + 1 ⇒ TEE (m) ≤ 6m + 3 .24. Доказать, что для чисел Фибоначчи справедливо Fn2 − Fn−1 Fn+1 = (−1) n , n = 1,2,...Решение. Докажем по индукции: очевидно, что для n = 1 равенство верно; пусть оноверно для n − 1 , т.е. Fn2−1 − Fn−2 Fn = (−1) n−1 ; докажем для n:Fn2 − Fn−1 Fn+1 = (Fn−1 + Fn−2 ) − Fn−1 (Fn + Fn−1 ) =14243142432FnFn +1= Fn2−1 + 2 Fn−1Fn−2 + Fn2−2 − Fn−1 Fn − Fn2−1 = 2 Fn−1Fn−2 + Fn2−2 − Fn−1 (Fn−1 + Fn−2 ) =14243Fn= Fn−1Fn−2 + Fn2−2 − Fn2−1 = Fn−2 (Fn−1 + Fn−2 ) − Fn2−1 = Fn−2 Fn − Fn2−1 = −(−1) n−1 = (−1) n25.
Доказать, что уравнение ax + by = c имеет решения в целых числах тогда и только тогда,когда d = НОД(a, b) делит c . Доказать, что если x0 , y0 решение, то все решенияbaописываются формулами x = x0 + t , y = y0 − t , t = 0,±1,±2,...dd26. Доказать, что si и tiпростые.(i = 0,1,..., n + 1)из расширенного алгоритма Евклида взаимноУказание:⎡− q1 1⎤⎡− qi−1 1⎤ ⎡ ti=⎢ 1 0⎥ × ... × ⎢ 10⎥⎦ ⎢⎣ si⎣⎦⎣ti−1 ⎤si−1 ⎥⎦27. Показать, что для бинарного поиска количество сравнений нельзя однозначноопределить по n, но есть такие n (бесконечно много), для которых можно ( ⎣log 2 n ⎦ + 1 ).28.
Есть плоскость и ортонормированный базис ( x, y ) . P1 , P2 ,..., Pn — заданный n-угольник.Требуется привести алгоритм определения, принадлежит ли точка Q многоугольнику, сосложностью Θ(log n) .29. Имеется 3n монет, одна из которых фальшивая. Есть чашечные весы. Известно, чтофальшивая монета легче остальных. За n взвешиваний требуется найти фальшивую.Алгоритм решения: на каждом этапе алгоритма все монеты делятся на 3 равные части,веса первых двух из которых сравниваются с помощью весов. Если веса равны, тофальшивая монета в третьей части и алгоритм повторяется для неё.
Если привзвешивании оказывается, что одна из частей весит меньше, то фальшивая монетанеобходимо там, следовательно, алгоритм применяется повторно уже к части сфальшивой монетой. Очевидно, что если изначально монет 3n , то за n взвешиванийфальшивая монета определяется однозначно. Требуется обобщить алгоритм на62⎡n⎤ ⎡n⎤⎡n⎤произвольное число монет: разбиение производится на ⎢ ⎥ , ⎢ ⎥ и n − 2 ⎢ ⎥ , и⎢3⎥ ⎢3⎥⎢3⎥взвешиваются первые две. Показать, что сложность по числу взвешиваний в этом случаесоставит ⎡log 3 n⎤ .⎢n⎥ ⎢n⎥⎢n⎥30. Ситуация как в предыдущей задаче, но разделение происходит на ⎢ ⎥ , ⎢ ⎥ и n − 2 ⎢ ⎥ .⎣3⎦ ⎣3⎦⎣3⎦Показать, что ∃n , для которых потребуется > ⎡log 3 n ⎤ взвешиваний.Решение.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
