Лекции о сложности алгоритмов. С. А. Абрамов (1121249), страница 27

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 27)

конкретного массива длины n.) Тогда в соответствии с принципом Яо сложность этой рандомизированной сортировки не может быть меньшечем log2 n!, так как при равномерном распределении вероятностейЗадачина Πn для сложности в среднем детерминированных алгоритмов сортировки мы имеем в силу предложения . нижнюю границу log2 n!при любом n. Задачи.

Для обсуждавшихся в задаче  алгоритмов сортировки вагонов функция 3n − 1 является нижней границей их сложности, откудаследует, что тот алгоритм, который требуется указать в задаче , является оптимальным в рассматриваемом классе.. Для сложности класса обсуждавшихся в задаче  алгоритмовпоиска двери в стене функция n является асимптотической нижнейграницей, откуда следует, что тот алгоритм, который требуется указать в задаче , является оптимальным по порядку сложности в рассматриваемом классе.. (Продолжение предыдущей задачи.) Для поиска двери можно указать класс A алгоритмов, каждый из которых определяетсянекоторым целым k ¾ 2: путник делает k шагов вправо, и если дверьне найдена, то возвращается назад и делает k шагов влево, и опятьвозвращается назад, если дверь не найдена; затем делает k 2 шаговвправо, возвращаясь назад в случае неуспеха, затем k 2 шагов влево и т.

д. Таким образом, A = {A2 , A3 , ...}, и для сложности по числушагов имеем TAk (n) = 3n, если k = n, и TAk (n) > 3n, если k 6= n. Какследствие, в классе A нет оптимального алгоритма, но каждый алгоритм из этого класса является оптимальным в нем по порядку сложности.Указание. Пусть m таково, что km−1 < n ¶ km . Возможно, что потребуетсячисло шагов, равное 2(k + k2 + ... + km ) + 2(k + k2 + ... + km−1 ) + n.. Нарисовать дерево быстрой сортировки для случая n = 3, считая, что первый элемент всегда выбирается в качестве разбивающего.. Дать другое доказательство предложения .. Рассмотретьпоследовательности из нулей и единиц, соответствующие результатам всех проводимых сравнений в процессе применения сортировкик массивам длины n (каждому массиву сопоставляется своя последовательность).Указание.

Если некоторый алгоритм сортировки требует не более h(n)сравнений, то длина каждой из последовательностей не превосходит h(n),и общее число последовательностей не превосходит 2h(n) .Дополнительные примеры применения принципа Яо можно найти в [, гл. ]. Глава . Нижняя граница сложности. Оптимальные алгоритмы. Аналогично предыдущей задаче, дать другое доказательствопредложения ... Как уже отмечалось (со ссылкой на приложение D), n являетсянижней границей сложности как по числу аддитивных операций, таки по числу умножений для класса алгоритмов, вычисляющих значение полинома an x n + ...

+ a1 x + a0 с помощью операций сложения, вычитания и умножения (при рассмотрении числа n как размера входаx, a0 , a1 , ..., an ). Означает ли это, что при вычислении любого фиксированного полинома p(x) степени n при заданном значении переменной x потребуется не менее n аддитивных операций и n умножений?Указать такие нижние границы сложности (по числу аддитивных операций и по числу операций умножения) алгоритмов вычисления поn Pnлиномаx k , которые растут при n → ∞ существенно медленнее,k =0kчем n..

Имеется плитка шоколада размера k × l клеток, которую требуется разломать на отдельные клетки. Каждый разлом применяется к одному куску плитки и производится по прямой линии. Затраты каждого алгоритма решения этой задачи применительно к конкретной плитке измеряются числом потребовавшихся разломов. Указать оптимальный алгоритм решения этой задачи и выписать егосложность.

Числа k, l считаются параметрами размера входа алгоритмов.. Если условно изобразить элементы массива длины n точкамина плоскости, соединяя отрезками те из них, которые непосредственно сравнивались в процессе некоторого алгоритма поиска, — скажем,поиска наименьшего элемента, одновременного поиска наибольшегои наименьшего элементов, поискаl m k-го по величине элемента (в частn-го элемента), — то получающийсяности, поиска медианы, т. е.2граф должен быть связным, иначе мы бы ничего не могли сказатьо том, как соотносятся между собой элементы из разных компонент.Показать, что для всех алгоритмов поиска, сопоставляющих указанным (неявным) образом связные графы конкретным массивам, n − 1является нижней границей сложности по числу сравнений (как в худшем случае, так и в среднем); в частности, это верно для алгоритмовпоиска медианы.Указание.

Дерево с n вершинами имеет n − 1 ребро.. Рассмотрим класс алгоритмов поиска k первых (меньших) повеличине элементов массива без установления порядка между найденными элементами и класс алгоритмов поиска k-го по величинеЗадачиэлемента. Как обычно, имеется в виду поиск с помощью сравнений.Доказать, что любая нижняя граница сложности по числу сравненийалгоритмов первого класса является нижней границей и для второгокласса.. Дать доказательство предложения ., построенное по той жесхеме, что и доказательство предложения ..Указание.

Рассмотреть тройки множеств (A, B, C), включая в A на каждомэтапе алгоритма все те элементы, которые еще не сравнивались, в B — всете, которые участвовали в сравнениях и всегда оказывались меньшими,в C — все те, которые участвовали в сравнениях и в некоторых оказывалисьбо́льшими.. Доказать содержащееся в доказательстве предложения . утверждение, что после первого сравнения постоянно будет выполненоb ¾ 1, c ¾ 1.. В классе алгоритмов вычисления an с помощью умножений (aфиксировано, n ∈ N) при рассмотрении n в качестве размера входасуществует оптимальный алгоритм. То же самое — при рассмотренииm = λ(n) в качестве размера входа..

Бинарный алгоритм возведения в степень n не является оптимальным по числу умножений и при использовании m = λ(n) в качестве размера входа.Указание. Рассмотреть алгоритм, который для всех n 6= 15 работает какбинарный алгоритм, а при n = 15 — несколько быстрее (см. задачу ), и показать, что такой алгоритм при m = 4 имеет сложность меньшую, чем бинарный.. (Продолжение задачи .) Является ли оптимальным по порядку сложности бинарный алгоритм возведения в степень n при использовании m = λ(n) в качестве размера входа?.

Рассмотренный в задаче  алгоритм поиска фальшивой монеты, требующий в худшем случае не более ⌈log3 n⌉ взвешиваний,является оптимальным для худшего случая.. Нижней границей сложности любого алгоритма деления отрезка на n равных частей с помощью циркуля и линейки (см. задачу ) при рассмотрении числа n в качестве размера входа является,n−1.в частности,2. Отсутствие указания основания логарифма в (.) являетсякорректным.. Функция log2 (n + 1) является нижней границей сложности всреднем алгоритмов поиска места элемента в упорядоченном массиве Глава . Нижняя граница сложности.

Оптимальные алгоритмыдлины n с помощью сравнений (считаем, что в диапазоне от 1 до1).n + 1 место может быть любым с одинаковой вероятностьюn+1Указание. Для доказательства воспользоваться предложением ... (Продолжение предыдущей задачи.) Алгоритм бинарного поиска является оптимальным в среднем по порядку сложности в классеалгоритмов поиска места элемента с помощью сравнений.. Алгоритм, описанный в задаче , является оптимальным какв худшем случае, так и в среднем.. Пусть ¯T¯QS (n) и ¯T¯opt (n) — сложности в среднем быстрой сортировки и оптимальной в среднем сортировки. Верно ли, что ¯T¯QS (n) ∼∼¯T¯opt (n)? Если нет, то можно ли подобрать константу c такую, что¯T¯Q (n) ∼ c¯T¯opt (n)?.

Утверждение теоремы . перестает быть верным, если егоизменить, удалив условие, что τ < ∞ всюду на рассматриваемом вероятностном пространстве: при выполнении всех остальных условий∞Pможет оказаться, что τ = ∞ при том, чтоhk имеет конечное значение.k =1Указание. Рассмотреть постоянные величины ξk =1, k = 1, 2, ... ,k(k + 1)взяв hk = ξk для всех k; при любом q ¾ 1 получается противоречие с измененным утверждением. . Функция log2 (n + 1) является нижней границей сложности рандомизированных алгоритмов поиска места элемента в упорядоченном массиве длины n с помощью сравнений.

(Предполагается, чтокаждый из рассматриваемых рандомизированных алгоритмов можетбыть задан как конечное множество детерминированных алгоритмовпоиска места элемента в упорядоченном массиве длины n, с приписанными этим детерминированным алгоритмам вероятностями,в сумме дающими единицу; при этом такое вероятностное пространство алгоритмов не должно зависеть от конкретного входа размера n.)Эта задача сообщена автору А.

В. Бернштейном.Глава Битовая сложность§ . Битовые операцииКаждый алгоритм строится на основе некоторого фиксированногонабора базовых операций, и, согласно определениям из § , алгебраическая сложность алгоритма рассматривается при допущении, чтозатратность операций не зависит от размеров операндов. С позицийкомпьютерной арифметики это допущение вполне приемлемо, есликаждый из операндов умещается в одном слове памяти. Но оно перестает быть приемлемым, если разрешаются операнды любой длиныи вычисления проводятся в рамках арифметики многократной точности (арифметики длинных чисел).

Характеристики

Список файлов лекций