С.А. Абрамов - Вычислительная сложность алгоритмов (лекции) (1121252), страница 9

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

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

рассмотреть аналогичное рекуррентноенеравенство с ≥ . В этом случае будет справедливо предложение, аналогичное доказанному,за исключением того, что в этом случае f (n) ≥ t (⎣log 2 n ⎦) (доказывается аналогично).В случае, когда для сложности задаётся рекуррентное равенство ( T (n) = ... ), то его можнорассматривать как систему неравенств T (n) ≤ ...

и T (n) ≥ ... . После чего будут полученысоотношения видаt (⎣log 2 n ⎦) ≤ f (n) ≤ t (⎡log 2 n ⎤)Границы очень тесные, откуда получаем хорошую оценку.41Попробуем описать класс массивов, на которых алгоритм (MS) будет работать дольше всего.Для этого достаточно рассмотреть действие алгоритма на перестановках. Назовёмперестановку критичной, если на ней достигается максимум сложности алгоритма слияния.Пусть x1 , ...

, x⎣ n ⎦ и y1 , ... , y⎡n ⎤ — критичные перестановки. Тогда z1 , ... , zn равные222 x1 , ... , 2 x⎣n ⎦ , 2 y1 − 1, ... , 2 y⎡ n ⎤ − 122(*)является перестановкой (доказать этот факт предлагается читателю) и для неё алгоритм⎛⎢n⎥⎞⎛⎡n⎤⎞сортировки слияниями потребует ровно TMS ⎜⎜ ⎢ ⎥ ⎟⎟ + TMS ⎜⎜ ⎢ ⎥ ⎟⎟ + n − 1 сравнений. Отсюда⎝⎣2⎦⎠⎝⎢2⎥⎠можно вывести, что для сложности алгоритма сортировки слияниями можно писать⎧0, n = 1⎪TMS (n) ≥ ⎨ ⎛ ⎢ n ⎥ ⎞⎛⎡n⎤⎞⎪TMS ⎜⎜ ⎢ 2 ⎥ ⎟⎟ + TMS ⎜⎜ ⎢ 2 ⎥ ⎟⎟ + n − 1, n > 1⎝⎢ ⎥⎠⎩ ⎝⎣ ⎦⎠Наряду с операциями сравнения мы можем рассмотреть сложность по перемещениям. Длясложности алгоритма сортировки слияниями по числу перемещений будет иметь местоследующее соотношение:⎧0, n = 1~⎪TMS (n) = ⎨ ~ ⎛ ⎢ n ⎥ ⎞ ~ ⎛ ⎡ n ⎤ ⎞n , n >1⎪TMS ⎜⎜ ⎢⎣ 2 ⎥⎦ ⎟⎟ + TMS ⎜⎜ ⎢⎢ 2 ⎥⎥ ⎟⎟ + {⎠⎝⎠ на слияние⎩ ⎝Ассоциированным соотношением в этом случае будет⎧0, k = 0t (k ) = ⎨k⎩2t (k − 1) + 2 , k > 0откуда получаем, что t (k ) = Θ(n log n) .Отметим, что рекурсия предполагает использование стека отложенных задач.

Ранее былопоказано, что при хорошей стратегии выбора текущей задачи можно добиться того, чточисло отложенных задач (сохранённых в стеке) не превзойдёт log 2 n (выбирать следуетболее простую, сложную откладывая в стек).Нередко ϕ (n) (см. предложение) не известно в явном виде, а известна лишь оценка:ϕ (n) = O(ξ (n) ) . Как тут быть? На самом деле, особой сложности с этим нет. Рассмотримтакой пример: в вычислительной геометрии есть задача о выпуклой оболочке (на плоскостизаданы точки и требуется найти такой выпуклый многоугольник, который охватывал бы всеточки и обладал при этом наименьшей площадью).Вообще говоря, здесь присутствуют 2 задачи, т.к.

искомый многоугольник можно выдаватькак упорядоченный набор вершин (например, с обходом по часовой стрелке начиная снекоторой), либо просто набором точек, хотя в данном контексте это не важно. Существует42множество алгоритмов, решающих поставленную задачу. В основе их лежит алгоритмпостроения выпуклого пересечения двух выпуклых многоугольников со сложностьюO(n1 + n2 ) , где n1 и n2 — число вершин в данных многоугольниках. Пусть такой алгоритм унас есть. Будем строить выпуклую оболочку следующим образом: разобьём данные n точек⎢n⎥ ⎡n⎤на две группы ⎢ ⎥ и ⎢ ⎥ , для каждой из которых построим выпуклую оболочку и применим⎣2⎦ ⎢2⎥алгоритм построения пересечения.

Тогда для сложности такого алгоритма получим:⎧0, n = 1⎪⎪сложность алг.пересеченияT ( n) = ⎨678⎛⎡n⎤⎞⎛⎢n⎥⎞⎪T ⎜⎜⎟ + T ⎜⎜ ⎢ ⎥ ⎟⎟ + O(n) , n > 1⎪⎩ ⎝ ⎢⎣ 2 ⎥⎦ ⎟⎠⎝⎢2⎥⎠Распишем O(n) по определению: ∃C > 0 : O(n) ≤ Cn , тогда получим⎧0, n = 1⎪T ( n) ≤ ⎨ ⎛ ⎢ n ⎥ ⎞⎛⎡n⎤⎞⎪T ⎜⎜ ⎢ 2 ⎥ ⎟⎟ + T ⎜⎜ ⎢ 2 ⎥ ⎟⎟ + Cn, n > 1⎝⎢ ⎥⎠⎩ ⎝⎣ ⎦⎠Соответствующее ассоциированное уравнение будет иметь вид⎧0, k = 0t (k ) = ⎨k⎩2t (k − 1) + C ⋅ 2 , k > 0Сильно ли нам портит дело то, что мы не знаем значение величины константы C?Оказывается, что не очень, так как в любом случае рекуррентное соотношение имеет частноерешение вида p (k )2 k , где p(k ) — многочлен первой степени, и, следовательно, для t (k )будет верна оценка t (k ) = O(k 2 k ) и для сложности получаем T (n) = O(n log n) .

О том, можноли строить выпуклую оболочку быстрее, поговорим позже.Давайте посмотрим на задачи, которые мы знаем, с позиции рассматриваемого метода.Для алгоритма возведения в степень (RS) можно написать следующую вещь:⎧0, если n = 1⎪TRS (n) ≤ ⎨ ⎛ ⎢ n ⎥ ⎞⎪TRS ⎜⎜ ⎢ 2 ⎥ ⎟⎟ + 1 + 1, n > 1⎩ ⎝⎣ ⎦⎠где одна из единиц во второй строке идёт на возведение в квадрат и ещё одна быть может наумножение уже накопленного. Второй единицы может не быть, но из-за знака ≤ это ничемуне противоречит.Ассоциированное уравнение в этом случае будет иметь вид:⎧0, k = 0t (k ) = ⎨⎩t (k − 1) + 2, k > 0решением которого будет t (k ) = 2k ⇒ TRS (n) ≤ 2 ⎡log 2 n ⎤ .

Ранее для этого алгоритма мыполучали 2⎣log 2 n⎦ , но новая оценка не на много хуже прежней.Рассмотрим ещё один пример: алгоритм бинарного поиска (BS). Для него можно написать43⎧1, n = 1⎪≤ ⎨ ⎛⎢n⎥⎞⎪TBS ⎜⎜ ⎢ 2 ⎥ ⎟⎟ + 1, n > 1⎩ ⎝⎣ ⎦⎠TBS⎢n⎥Когда мы производим одно сравнение, то мы можем перейти к поиску в массиве длины ⎢ ⎥⎣2⎦⎢n⎥или ⎢ ⎥ − 1 , поэтому для справедливости верхнего соотношения нужно быть уверенным, что⎣2⎦TBS (n) с ростом n не убывает. Откуда такая уверенность? Конкретно для алгоритмабинарного поиска этот факт можно доказать по индукции, но сложность произвольногоалгоритма, вообще говоря, не обладает этим свойством. Алгоритм возведения в степень, кпримеру, не обладает таким свойством (в 7-ю степень возвести труднее, чем в 8-ю).Возвращаясь к алгоритму бинарного поиска, если всё сделать по предложенному рецепту, тоассоциированное уравнение будет иметь вид:⎧1, k = 0t (k ) = ⎨⎩t (k − 1) + 1, k > 0Единица, стоящая в правой части рекуррентного соотношения, является корнемхарактеристического уравнения, поэтому для сложности будем иметь TBS (n) ≤ ⎡log 2 n ⎤ + 1 .Ранее была получена оценка чуть лучше: с полом вместо потолка.Перейдём к алгоритмам более арифметическим.

Иногда, если речь идёт об умножении целыхчисел, то бывает удобно, если количество цифр в двоичной записи чисел равно 2 k . Приработе с матрицами — хорошо, если их порядок равен 2 k . Оказывается, что если прибегнутьк такому приёму, что приписать к числу некоторое количество незначащих нулей так, чтодлина в итоге станет равна 2 k , то это позволяет умножать числа очень быстро. Еслиперемножаем две матрицы A и B, то можно дописать нужное количество нулей:⎡ A 0⎤ ⎡ B 0⎤ ⎡ AB 0⎤⎢ 0 0⎥ × ⎢ 0 0⎥ = ⎢ 0 0⎥⎣⎦ ⎣⎦ ⎣⎦чтобы порядок стал 2 k . Рассмотрим 2 алгоритма такого рода.Алгоритм умножения Карацубы (KM).

Рассмотрим двоичные числа a и b длины n = 2l(одинаковая и чётная): a = e ⋅ 2l + f , b = g ⋅ 2l + h , где e, f, g, h — двоичные числа длины l.А.Карацубе удалось составить алгоритм умножения двух чисел длины 2l, использующий 3умножения:ab = eg ⋅ 2 2l + ((e + f )( g + h ) − eg − fh ) ⋅ 2l + fhв то время как обычное раскрытие скобок(e ⋅ 2 + f )(g ⋅ 2 + h) = eg ⋅ 2 + (eh + fg )⋅ 2ll2ll+ fhтребует 4 умножения.Если посмотреть на формулу Карацубы, то там нужно вычислить лишь eg , fh и(e + f )(g + h ) . Рассмотрим внимательнее последнее произведение. Обозначим e + f = e1 2l + f1 ,g + h = g1 2l + h1 , где e1 и g1 — однобитовые числа, а битовая длина f1 и h1 не превосходит l.(e + f )( g + h) = e1 g1 2 2l + (e1h1 + g1 f1 )2l +f1h1123вычисляетсярекурсивно44Все остальные операции (сложения, сдвиги) можно оценить через O(n) .Для начала рассмотрим случай n = 2 k (на вход подаются два числа с одинаковой битовойдлиной равной 2 k ).

Тогда для сложности алгоритма Карацубы можно написать⎧1, k = 0T (k ) = ⎨⎩3T ( k − 1) + O ( 2 ), k > 0Так же, как и в случае с выпуклой оболочкой, можно перейти к рекуррентному неравенству⎧1, k = 0T (k ) ≤ ⎨k⎩3T (k − 1) + C ⋅ 2 , k > 0Ассоциированным уравнением будет⎧1, k = 0t (k ) = ⎨k⎩3t (k − 1) + C ⋅ 2 , k ≥ 1T (k ) ≤ t (k )Решение ассоциированного уравнениядоминирующий член) ⇒ T (k ) = O (3k ) .можнозаписатьвиде t (k ) = O (3k ) (берявТеперь перейдём к более общему случаю: пусть нам даны два числа произвольной длины.Пусть m — наибольшая из битовых длин этих чисел.

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

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