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

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

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

Каждый день бизнесмен дает черту одну монету, и в обменполучает любой набор монет по своему выбору, но меньшего достоинства. Видов монет конечное число; менять или получать деньгив другом месте бизнесмен по условиям сделки не может. Если у бизнесмена не остается монет достоинством выше минимального, онпроигрывает. На таких условиях рано или поздно бизнесмен терпитпоражение, каков бы ни был первоначальный запас его монет..

Имеется конечная последовательность нулей и единиц. Разрешается найти в ней группу 01 и заменить на 100...00 (при этомможно написать сколько угодно нулей). Доказать, что это преобразование не может быть произведено бесконечно много раз.Задачи. Алгоритм, приведенный в примере ., затрачивает O(log n)шагов..

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

Алгоритм препятствует слишком быстрому изъятию из рассмотрения отдельных вопросов.. Найти число операций прибавления единицы к r при выполнении алгоритма для заданного натурального nr := 0;for i = 1 to n dofor j = i + 1 to n dofor k = i + j − 1 to n do r := r + 1 ododod(иначе: определить, чему равно r). Формальное построение и последующее столь же формальное вычисление суммы по аналогии с проделанными в примере . привело бы к неправильному ответу (причина указывалась в §  в замечании к примеру .)..

Исследовать зависимость от целого n > 0 общего числа арифметических операций, требуемых алгоритмомl := 0;for i = 1 to n dofor j = 1 to ⌊log2 i ⌋ do l := l + i + j odod. Исследовать зависимость от n > 0 общего числа арифметических операций, требуемых алгоритмомl := 0;pfor i = 1 to ⌊ n⌋ doz := i ;while z > 1 do l := l + 1; z := 7z odod(значения z не обязательно целые).Глава Нижняя граница сложности алгоритмовнекоторого класса.

Оптимальные алгоритмы§ . Понятие нижней границы сложностиХорошо известно, что существуют алгоритмически неразрешимые задачи. Но если даже задача алгоритмически разрешима, то возможно,что сложность каждого из алгоритмов ее решения будет в определенном смысле достаточно высокой.Пример .. Рассмотрим задачу поиска наименьшего элементас помощью сравнений в массиве длины n.

Для того чтобы иметьоснования отсеять элемент массива как заведомо не являющийсянаименьшим, необходимо, чтобы этот элемент участвовал хотя быв одном сравнении и оказался бо́льшим. Мы должны отсеять n − 1элемент, а в каждом сравнении ровно один элемент оказываетсябо́льшим. Это означает, что потребуется не менее n − 1 сравнения.Введем основное понятие этой главы.Определение .. Пусть A — класс алгоритмов решения некоторой задачи. Пусть принято соглашение о том, в чем измеряютсязатраты алгоритмов и что считается размером входа, и пусть n — обозначение размера входа. Функция f (n) называется нижней границей сложности принадлежащих A алгоритмов, если для сложностиTA (n) любого A ∈ A мы имеем TA (n) ¾ f (n) при всех допустимых значениях размера входа n. (Если используются несколько параметровn1 , n2 , ..., nk размера входа, то нижняя граница — это, соответственно, функция аргументов n1 , n2 , ..., nk .)Это определение имеет смысл как для сложности в худшем случае,так и для сложности в среднем.

Далее в примерах этого и следующегопараграфов мы рассматриваем сложность в худшем случае; к сложности в среднем мы вернемся в § . Всюду будет рассматриваться вре-§ . Понятие нижней границы сложностименная сложность. Мы можем сформулировать обнаруженный прирассмотрении примера . факт следующим образом.Предложение .. Функция f (n) = n − 1 является нижней границей сложности алгоритмов поиска наименьшего элемента массивадлины n c помощью сравнений.(Иными словами, не существует такого алгоритма выбора наименьшего элемента массива длины n c помощью сравнений, сложность которого хотя бы для одного значения n была меньше чемn − 1.)В роли класса A здесь выступает класс алгоритмов поиска наименьшего элемента массива с помощью сравнений.

Если бы помимосравнений были допустимы какие-то еще операции, то, возможно,n − 1 уже не годилось бы в качестве нижней границы. Например, если было бы разрешено пользоваться операцией выбора наименьшегоиз нескольких элементов, то задачу можно было бы решить однойоперацией.Пример .. Рассмотрим класс алгоритмов сортировки с помощью сравнений. Если алгоритм работает для массивов любой длины, то, разумеется, можно рассмотреть этот алгоритм применительно к массивам некоторой фиксированной длины n. Любая сортировкас помощью сравнений может быть для каждого конкретного n изображена бинарным деревом. В корне и внутренних вершинах находятся выполняемые сравнения, в листьях выписаны результаты сортировки.

Априори в исходном массиве возможен любой порядок элементов, поэтому дерево будет иметь n! листьев. Если взять, например,сортировку простыми вставками, то при n = 2 ее можно изобразитьдеревом, представленным на рис. а. При n = 3 дерево принимаетвид, показанный на рис. б. Сложность в худшем случае для каждого n равна высоте соответствующего дерева (напомним, что высотойлиста называется число ребер в том единственном пути, который ведет от корня дерева к этому листу; высотой дерева называется максимум высот его листьев).

Если высота некоторого бинарного дереваравна h, то, очевидно, оно содержит не более 2h листьев (максимальное возможное число листьев достигается в случае полного бинарного дерева, которое имеет ровно 2h листьев). Поэтому если T(n) — этовременная сложность некоторой сортировки сравнениями, то должновыполняться неравенство2T (n) ¾ n!, Глава . Нижняя граница сложности. Оптимальные алгоритмыx1 < x2а)б)x1 < x201x1 , x2x2 , x101x2 < x3x3 < x101x3 < x2x1 < x3x1 , x2 , x31x1 , x3 , x2010x3 , x1 , x21x3 , x2 , x1x2 , x1 , x30x2 , x3 , x1Рис. .

Дерево сортировки простыми вставками для случаев а) n = 2и б) n = 3.откуда T(n) ¾ log2 n!; так как значение T(n) — целое число (мы измеряем сложность числом сравнений), то T(n) ¾ ⌈log2 n!⌉. Доказанноеможно сформулировать в виде предложения.Предложение .. Функция f (n) = ⌈log2 n!⌉ является нижней границей сложности алгоритмов сортировки массивов длины n c помощью сравнений.Отсюда можно вывести, например, следующее предложение.Предложение .. Пусть сложность T(n) некоторой сортировки по числу сравнений не превосходит n log2 n + cn, где c — некоторая константа. Тогда T(n) = n log2 n + O(n) и, как следствие, T(n) ∼∼ n log2 n.Доказательство. В силу предложения . и формулы (.) длявсех достаточно больших n мы имеем T (n) ¾ ⌈log2 n!⌉ > n log2 n − 2n,и, следовательно, n log2 n − 2n < T(n) ¶ n log2 n + cn. Отсюда следуеттребуемое.Это позволяет, например, заключить, что для сложности по числу сравнений сортировки фон Неймана имеет место оценка TvN (n) == n log2 n + O(n) и асимптотическое равенство TvN (n) ∼ n log2 n, — мыуже видели, что TvN < n⌈log2 n⌉ < n log2 n + n.§ .

Оптимальные алгоритмыДобавим, что никакая сортировка не может иметь сложность T(n)по числу сравнений, допускающую оценку αn log2 n + o(n log n), α < 1(в частности, оценку αn log2 n + O(n)), — это следует из того, что длявсех достаточно больших n выполнено T(n) > n log2 n − 2n.Пример .. Обратимся к задаче поиска места элемента в упорядоченном массиве длины n.Предложение ..

Функция f (n) = ⌈log2 (n + 1)⌉ является нижнейграницей сложности алгоритмов поиска места элемента в упорядоченном массиве длины n c помощью сравнений.Доказательство. Любой алгоритм поиска места элемента в упорядоченном массиве фиксированной длины n может быть изображенбинарным деревом. Число листьев такого дерева есть n + 1. Далеерассуждаем так же, как при доказательстве предложения ..Пример .. Рассмотрим задачу вычисления an с помощью умножений (пример .). Будем считать n размером входа. Затраты будемизмерять количеством умножений.Предложение ..

Функция f (n) = ⌈log2 n⌉ является нижней границей сложности алгоритмов вычисления an с помощью умножений.Доказательство. На каждом этапе алгоритма мы имеем вычисленный набор степенейam1 , am2 , ..., amk ,(.)при этом на начальном этапе набор состоит из одного элемента a1 .Выполнив одно умножение, мы, очевидно, не можем увеличить максимальный показатель m = max{m1 , m2 , ..., mk } более чем вдвое. Поэтому если определить на наборах вида (.) функцию L, равнуюlog2 n − log2 m, то в результате одного шага (одного умножения) этафункция не может уменьшиться больше чем на 1. В то же время значение этой функции на исходном наборе равно log2 n, а на итоговомнаборе она заведомо неположительна.§ .

Оптимальные алгоритмыНижняя граница сложности класса алгоритмов определяется не единственным образом. Например, f (n) = 0 всегда является нижней границей, равно как и любая отрицательная функция. Чем больше найденная нижняя граница, тем она нетривиальнее и ценнее. Сигналомо том, что мы не сможем построить нижнюю границу бо́льшую, чем Глава . Нижняя граница сложности. Оптимальные алгоритмыуже имеющаяся у нас нижняя граница f (n), может служить, например, наличие A ∈ A , для которого TA (n) = f (n). С такой ситуацией мысталкиваемся в предыдущем параграфе в примерах . и .. Известный нам алгоритм поиска наименьшего элемента и алгоритм бинарного поиска места элемента в упорядоченном массиве имеет каждыйсложность, совпадающую с найденной нижней границей.

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

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

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