С.А. Абрамов - Вычислительная сложность алгоритмов (1123766), страница 14
Текст из файла (страница 14)
Дан массив 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 ⎤ взвешиваний.Решение. Рассмотрим n = 3k − 1, k ≥ 2 . Для таких n получаем ⎡log3 n ⎤ = k . Посмотрим,сколько взвешиваний потребуется алгоритму. На первом шаге все монеты разделятся⎛⎢n⎥ ⎢n⎥⎢n⎥⎞на три части: ⎜⎜ ⎢ ⎥, ⎢ ⎥, n − 2⎢ ⎥ ⎟⎟ = (3k −1 − 1, 3k −1 − 1, 3k −1 + 1) . Пусть фальшивая монета⎣3⎦⎠⎝⎣3⎦ ⎣3⎦оказывается всегда в третьей части, тогда на втором шаге получаем следующие части:⎛ ⎢ 3k −1 + 1⎥ ⎢ 3k −1 + 1⎥ k −1⎢ 3k −1 + 1⎥ ⎞⎜⎢⎟ = (3k −2 , 3k −2 , 3k −2 + 1) и т.д.
На k-м шаге монеты,⎢, 3 + 1 − 2⎢⎥⎥⎥⎜⎟⎣ 3 ⎦⎠⎝⎣ 3 ⎦ ⎣ 3 ⎦разбиваются на следующие части: (1, 1, 2 ) , где фальшивая монета находится в третьегруппе, а значит необходимо для её выявления ещё одно взвешивание. Итого получаемk + 1 > ⎡log 3 n ⎤ = k взвешиваний.31. Имеется конечная последовательность из нулей и единиц. Разрешается заменять группу01 на 1 0{...0 . Доказать, что алгоритм завершается.сколькоугодно32. Чему равно r ?r:=0;for i=1 to n dofor j=i+1 to n dofor k=i+j to n dor:=r+1;odododРешение. Не трудно видеть, что можно изменить правые границы циклов, следующимобразом:r:=0;⎢ n − 1⎥dofor i=1 to ⎢⎣ 2 ⎥⎦for j=i+1 to n-i dofor k=i+j to n dor:=r+1;odododЭто не изменит семантики программы, но теперь каждый цикл проработает указанное⎢ n − 1⎥и составим сумму:количество раз.
Обозначим x = ⎢⎣ 2 ⎥⎦63xn −ir=∑∑ni =1 j =i +1k =i + jИзxn −ix∑1 = ∑ ∑ [n − (i + j ) + 1] = ∑ (n − 2i)i =1 j =i +1математическогоi =1анализаизвестнаxn + 1 − 2i⎛ n(n + 1)⎞= ∑⎜− i (2n + 1) + 2i 2 ⎟22⎠i =1 ⎝формула: 12 + 22 + ... + n 2 =n(n + 1)(2n + 1)6(устанавливается по индукции). Применим её и окончательно получим:xn(n + 1) 1 + xx( x + 1)(2 x + 1)⎛ n(n + 1)⎞r = ∑⎜− i (2n + 1) + 2i 2 ⎟ = x ⋅−⋅ x(2n + 1) +2223⎠i =1 ⎝33. Для задачи 4 доказать, что f (n) = 3n − 1 является нижней границей.Решение. Худший случай работы алгоритма сортировки заключается в максимальнойзагруженности тупика.
Очевидно, что в отдельно взятый момент времени вагоны втупике имеют одинаковые цвета (вагон отправляется в тупик, когда его цвет совпадаетс цветом последнего вагона формируемого состава, но тогда цвет вагонов в тупикедолжен совпадать с цветом текущего вагона, т.к. в противном случае была бывозможность операции ИЗ). Максимальная загрузка тупика возможна на n − 1 вагон, т.к.один вагон в любом случае должен быть отправлен МИМО. Для доказательствавозможности загрузки тупика на n − 1 вагон приведём пример: исходный составсостоит из n вагонов одного цвета подряд, после которых следуют n вагонов другогоцвета. В этой ситуации первый вагон перегоняется МИМО, а остальные n − 1 вагонпопадают в тупик.
Тогда для нижней границе получаем: 1 операция МИМО, n − 1операций В, каждая из которых в конечном итоге сопровождается операцией ИЗ, иоставшиеся n операций МИМО. Итого получаем: 1 + 2 ⋅ (n − 1) + n = 3n − 1 .34. Для задачи 5 доказать, что алгоритм с O(n) является оптимальным по порядкусложности.Решение. Т.к. любой алгоритм поиска двери допускает оценку Ω(n) , то алгоритм соценкой O(n) будет являться оптимальным по порядку сложности.35. Показать, что для сложностиΘ 2 max{ma ,mb } max{ma , mb } не верна.()алгоритма«наивного»умноженияоценка**36. Верна ли для алгоритма «наивного» деления оценка TND(ma , mb ) = Θ(ma mb ) ?37. Имеется массив из попарно различных элементов и требуется найти медиану — элемент,меньше и больше которого одинаковое число элементов (в случае чётного числаэлементов возможно отличие на 1).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
