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

, 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 — наибольшая из битовых длин этих чисел.

Далее подгоняем длины обоих чисел к2 ⎡log2 m ⎤ , приписывая незначащие нули. Тогда для сложности алгоритма получим:()()(TKM (m) = O 3⎡log2 m ⎤ = O 3log2 m = { log 2 m = log 2 3 ⋅ log 3 m } = O m log2 3)При этом log 2 3 = 1,58... < 2 . Если вспомнить алгоритм «наивного» умножения, то для негобыла получена оценка Θ(m 2 ) , поэтому алгоритм Карацубы в этом плане лучше.Чтобы иметь возможность сравнивать этот алгоритм с другими, нужно иметь для негооценку снизу. Её можно получить. Давайте подсчитаем общее число умноженийоднобитовых чисел. Их количество будет⎧1, k = 0⎩3τ (k − 1), k > 0τ (k ) ≥ ⎨()⇒ τ (k ) ≥ 3k , что даёт нам возможность написать TKM (m) = Θ m log2 3 .Далее речь пойдёт об алгоритме Штрассена для умножения матриц (SM).

Пусть A и B —квадратные матрицы. Если их порядки чётные ( n = 2l ), то мы можем их «разрезать»пополам:⎡AA = ⎢ 11⎣ A21A12 ⎤⎡B, B = ⎢ 11⎥A22 ⎦⎣ B21B12 ⎤B22 ⎥⎦Далее если мы попробуем их перемножить «в лоб», то нам потребуется 8 умножений матрицпорядка l. Штрассен предлагает алгоритм, использующий в этом случае 7 умножений, ночисло сложений в этом случае будет не меленькое:45X 1 = ( A11 + A22 )(B11 + B22 )X 5 = ( A11 + A12 )B22X 3 = A11 (B12 − B22 )X 7 = ( A12 − A22 )(B21 + B22 )X 2 = ( A21 + A22 )B11X 6 = ( A21 − A11 )(B11 + B12 )X 4 = A22 (B21 − B11 )C11 = X 1 + X 4 − X 5 + X 7C12 = X 3 + X 5C21 = X 2 + X 4C22 = X 1 + X 3 − X 2 + X 6C12 ⎤⎡CAB = ⎢ 11⎥⎣C21 C22 ⎦()(TSM (n) = Θ 7 ⎡log2 n ⎤ = Θ 7 log2 n)Пользуясь тем же приёмом, что и в алгоритме Карацубы, получим()TSM (n) = Θ n log2 7 , log 2 7 = 2,807...