С.А. Абрамов - Лекции о сложности алгоритмов (pdf) (1123764), страница 22

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

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

Известный нам алгоритм поиска наименьшего элемента и алгоритм бинарного поиска места элемента в упорядоченном массиве имеет каждыйсложность, совпадающую с найденной нижней границей. Эти алгоритмы являются оптимальными в смысле следующего определения.Определение .. Пусть A — класс алгоритмов решения некоторой задачи. Пусть принято соглашение о том, в чем измеряютсязатраты алгоритмов и что считается размером входа, и пусть n — обозначение размера входа.

Алгоритм A ∈ A называется оптимальнымв A , если TA (n) является нижней границей сложности алгоритмовиз A .Пример .. При получении нижней границы сложности и доказательстве оптимальности иногда бывает полезным привлечениефункций на наборах тех величин, которые возникают в процессе выполнения алгоритма, например, на наборах значений переменных,используемых алгоритмом.l m3n− 2 является нижнейПредложение .. Функция f (n) =2границей сложности алгоритмов одновременного выбора наибольшегои наименьшего элементов массива длины n c помощью сравнений.Доказательство.

Каждый этап выполнения произвольного алгоритма V, основанного на сравнениях и предназначенного для поисканаибольшего и наименьшего элементов массива, может быть охарактеризован четверкой (A, B, C, D) подмножеств множества исходныхэлементов {x1 , x2 , ..., xn }, где• A состоит из всех тех элементов, которые вообще не сравнивались;• B состоит из всех тех элементов, которые участвовали в некоторыхсравнениях и всегда оказывались бо́льшими;• C состоит из всех тех элементов, которые участвовали в некоторых сравнениях и всегда оказывались меньшими;• D состоит из всех тех элементов, которые участвовали в некоторых сравнениях, иногда оказываясь бо́льшими, а иногда — меньшими.Пусть a, b, c, d — количества элементов множеств A, B, C, D соответственно.

Исходная ситуация характеризуется равенствами a = n, b == c = d = 0. После завершения алгоритма должны выполняться равен-§ . Оптимальные алгоритмыства a = 0, b = c = 1, d = n − 2. После первого сравнения на протяжении всего выполнения алгоритма постоянно будут иметь место неравенства b ¾ 1, c ¾ 1.Все сравнения, совершаемые при выполнении алгоритма V , можно разбить на типы, обозначаемые AA, AB, AC, AD, BB, BC, BD, CC,CD, DD, например: сравнение принадлежит типу AB, если один изсравниваемых элементов берется из A, другой — из B, и т. д. Исходя изэтого, можно выписать все возможные изменения четверки (a, b, c, d)под действием сравнений разных типов:AA : (a − 2, b + 1, c + 1, d),AB : (a − 1, b, c + 1, d) | (a − 1, b, c, d + 1),AC : (a − 1, b + 1, c, d) | (a − 1, b, c, d + 1),AD : (a − 1, b + 1, c, d) | (a − 1, b, c + 1, d),BB: (a, b − 1, c, d + 1),BC : (a, b − 1, c − 1, d + 2) | (a, b, c, d),BD : (a, b − 1, c, d + 1) | (a, b, c, d),CC : (a, b, c − 1, d + 1),CD : (a, b, c − 1, d + 1) | (a, b, c, d),DD : (a, b, c, d)(вертикальная черточка здесь означает «или»).

Рассмотрим функцию3L(a, b, c, d) = a + b + c − 2. Для начальной и конечной стадий имеем23L(n, 0, 0, 0) = n − 2 и L(0, 1, 1, n − 2) = 0 соответственно.2Каждое сравнение типов AA, BB, CC понижает значение L на 1,т. е. дает ∆ L = −1. Выпишем все возможные значения ∆ L при выполнении сравнений различных типов:AA, BB, CC :BD, CD :−1,−1 | 0,3212AB, AC :− |− ,BC :−2 | 0,AD :− ,DD :0.12Сравнения, относящиеся к типам AB, AC, BC, могут приводитьк ∆ L < −1, но это не может быть гарантировано никаким специальным выбором элементов из соответствующих множеств четверки Глава .

Нижняя граница сложности. Оптимальные алгоритмы(A, B, C, D), даже если принимать во внимание результаты всех сравнений, в которые были вовлечены конкретные элементы этих множеств. Например, сравнение типа AB в том случае, когда выбранныйэлемент из A оказывается больше выбранного элемента из B, преобразует (a, b, c, d) в (a − 1, b, c, d + 1), что дает ∆ L < −1.

Но результатыпредшествующих сравнений не дают оснований для отметания возможности того, что выбранный элемент из B равен max{x1 , x2 , ..., xn }(ибо этот элемент оказался бо́льшим во всех сравнениях, в которые1он был вовлечен). Но тогда будет выполнено ∆ L = − . Аналогичным2образом дело обстоит для сравнений, принадлежащих типам AC, BC.Поэтому, рассматривая поведение алгоритма V в худшем случае, надо считать, что на всех этапах ∆ L ¾ −1. Но тогда для достижения равенства L(a, b, c, d) = 0 потребуется не менее ⌈ L(n, 0, 0, 0)⌉ сравнений.Это значит,l m что общее число сравнений в худшем случае не меньше,3nчем− 2.2Представленный в приложении A алгоритм одновременного поисканаибольшего и наименьшегоэлементов массива, требующий в худшемl m3nслучае не более− 2 сравнений, является оптимальным  .2Наряду с алгоритмами поиска наименьшего элемента, бинарного поиска места элемента в упорядоченном массиве и алгоритма одновременного поиска наибольшего и наименьшего элементов массива примером оптимального алгоритма может служить алгоритм(«схема») Горнера вычисления значения полинома в данной точке(см.

приложение D).Для произвольного класса A оптимальный алгоритм может и несуществовать: если, например, A содержит ровно два алгоритма,A1 , A2 , и при этом A1 имеет низкую сложность при четных значениях целочисленного размера входа n и высокую — при нечетных,а A2 — наоборот, то, очевидно, ни A1 , ни A2 не будут оптимальными в A . Ясно, что если оптимальные алгоритмы в классе A существуют, то их сложности совпадают: из неравенств TA1 (n) ¾ TA2 (n)и TA2 (n) ¾ TA1 (n) следует, что TA1 (n) = TA2 (n). Несколько более содержательный пример можно найти в задаче .В отличие от поиска наименьшего элемента, поиска места в упорядоченном массиве и одновременного поиска наибольшего и наиЭтот алгоритм и идея использования четверок (A, B, C, D) в доказательстве его оптимальности были предложены И.

Полом в [], но при этом убывающие функции в егодоказательстве не привлекались, из-за чего потребовались дополнительные словесныемотивации.§ . Оптимальные алгоритмыменьшего элементов, задача сортировки не столь проста: те алгоритмы, которыми пользуются на практике для ее решения, не являются,строго говоря, оптимальными (см. приложение F).Заметим при этом, что для каждого конкретного n за конечноечисло шагов может быть найдено наименьшее число сравнений, достаточное в худшем случае для сортировки n элементов, а вместес ним и алгоритм сортировки с такой сложностью. Это следует из того, что при каждом конкретном n алгоритм сортировки может бытьпредставлен бинарным деревом. Можно порождать одно за другимвсе бинарные деревья с высотой, не превосходящей ⌈log2 n!⌉, в вершинах каждого такого дерева различными способами расставлять выражения вида xi < x j , где i, j ¶ n, а в листьях — различные перестановки длины n. Для каждого размеченного таким способом дереванужно проверить, действительно ли каждая ветвь приводит именнок тому порядку, который указан в листе, и что все возможные порядки охвачены.

Из всех «правильных» деревьев выбирается имеющеенаименьшую высоту. Оно определяет оптимальный алгоритм для заданного n.Таким образом, мы имеем алгоритм, который, исходя из n > 0,строит оптимальный по числу сравнений алгоритм сортировки массивов из n элементов (алгоритм строит алгоритм). Этот алгоритмпостроения оптимального алгоритма сортировки требует огромнойработы, даже если применить все средства экономии перебора.

Этотпример еще раз показывает, что понятие алгебраической сложноститребует осторожного обращения, — объем неучитываемых операцийможет превзойти разумные пределы.Бинарный алгоритм возведения в степень n также не являетсяоптимальным по числу умножений при использовании n в качестверазмера входа (см. задачу ), хотя и легко показать, что для случая n = 2k при рассмотрении k в качестве размера входа оптимальность имеет место: из предложения . следует, что возведение в степень n = 2k не может быть выполнено с затратами меньшими, чемk умножений, а бинарный алгоритм обходится в точности этим числом умножений.В общем же случае, как и многие известные алгоритмы сортировки, бинарный алгоритм возведения в степень оптимален лишьв некотором асимптотическом смысле, о чем пойдет речь в следующем параграфе.Если затраты для каждого входа являются целыми числами (например, они являются количеством выполненных операций), то дляфиксированного размера n0 входа в рассматриваемом классе A ал- Глава .

Нижняя граница сложности. Оптимальные алгоритмыгоритмов решения некоторой задачи P существует такой, сложностькоторого при n = n0 есть минимум сложностей всех алгоритмов из A .Можно определить такой минимум для любого значения n, получаемую таким способом функцию от n иногда называют сложностьюзадачи P по отношению к классу алгоритмов A . Важно, что при разных n минимумы могут доставляться разными алгоритмами из A(см. задачу ). В дальнейшем мы не будем касаться этих вопросов.§ . Асимптотические нижние границы.

Алгоритм,оптимальный по порядку сложностиИзвестно не очень много алгоритмов, оптимальных в смысле определения .. Рассмотрим дополнительно понятие алгоритма, оптимального по порядку сложности.Определение .. Пусть A — класс алгоритмов решения некоторой задачи. Пусть принято соглашение о том, в чем измеряютсязатраты алгоритмов и что считается размером входа, и пусть n — обозначение размера входа. Функция f (n) называется асимптотическойнижней границей сложности принадлежащих A алгоритмов, еслидля сложности TA (n) любого A ∈ A мы имеем TA (n) = Ω( f (n)). (Если используются несколько параметров n1 , n2 , ..., nk размера входа, тоасимптотическая нижняя граница — это, соответственно, функция аргументов n1 , n2 , ..., nk .) Алгоритм A ∈ A называется оптимальным попорядку сложности в A , если TA (n) является асимптотической нижней границей сложности алгоритмов из A .Очевидно, что любая неотрицательная нижняя граница сложности является и асимптотической нижней границей, и что любой оптимальный алгоритм является оптимальным по порядку сложности.Ниже в примере . мы увидим, что может существовать несколькооптимальных по порядку сложности в A алгоритмов.

Однако сложности таких алгоритмов оказываются величинами одного порядка.Теорема .. Пусть A, B ∈ A оптимальны по порядку сложностив A . Тогда TA (n) = Θ(TB (n)).Доказательство. Так как алгоритм A оптимален по порядку сложности, имеем TB (n) = Ω(TA (n)) или, что то же самое, TA (n) = O(TB (n)),что вместе с TA (n) = Ω(TB (n)) (алгоритм B оптимален по порядкусложности) дает TA (n) = Θ(TB (n)).§ . Асимптотические нижние границыУкажем достаточное условие оптимальности алгоритма по порядку сложности.Теорема .. Если функция f (n) является асимптотической нижней границей сложности принадлежащих классу A алгоритмов и еслиалгоритм A ∈ A таков, что TA (n) = O( f (n)), то этот алгоритм оптимален в A по порядку сложности и TA (n) = Θ( f (n)).Доказательство. Для произвольного B ∈ A имеем TB (n) = Ω( f (n));учитывая, что TA (n) = O( f (n)), получаем TB (n) = Ω(TA (n)), т.

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

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