С.А. Абрамов - Лекции о сложности алгоритмов (pdf) (1123764), страница 34
Текст из файла (страница 34)
Если в условиях теорем . и . предположить, что c = 0, то получим соответственно f (n) = O(nlog2 (v +w) ) иf (n) = Ω(nlog2 (v +w) ).Пример .. Вновь рассмотрим сложности рекурсивной сортировки слияниями и бинарного возведения в степень. Уравнение(.) представим как систему двух неравенств со знаками соответственно ¶ и ¾. Применяя к ним теоремы . и . (v + w = 2,log2 (v + w) = d = 1), из первой теоремы получаем TeMS (n) = O(n log n),из второй — TeMS (n) = Ω(n log n). В итоге имеем TeMS (n) = Θ(n log n).Аналогичным образом представим в виде системы двух неравенствуравнение (.). Заменим в правой части n − 1 на n в случае ¶ и наnв случае ¾. Очевидно, что полученные неравенства являются след2ствиями исходных. С помощью теорем . и . (вновь v + w = 2,log2 (v + w) = d = 1) получаем TMS (n) = O(n log n) и TMS (n) = Ω(n log n).В итоге имеем TMS (n) = Θ(n log n).Сложность рекурсивной сортировки слияниями как по числу сравнений, так и по числу перемещений элементов массива допускаетоценку Θ(n log n).Применяя теоремы . и . к (.), (.) (теперь v + w = 1,log2 (v + w) = d = 0), получим TRS (n) = O(log n) и TRS (n) = Ω(log n).В итоге получаем TRS (n) = Θ(log n).Асимптотические оценки TMS (n) = Θ(n log n), TeMS (n) = Θ(n log n),TRS (n) = Θ(log n) можно было бы получить и из выведенных ранеенеравенств (.), (.), (.).
Этот пример демонстрирует лишьто, что теоремы о рекуррентных неравенствах позволяют быстро получать асимптотические оценки непосредственно из первоначальныхрекуррентных неравенств.Пример .. Известен алгоритм построения выпуклой оболочки объединения двух выпуклых многоугольников, имеющих соответственно n1 и n2 вершин, со сложностью O(n1 + n2 ) по общему числуопераций, n1 + n2 рассматривается как размер входа этого алгоритма(см. задачу ).
Стратегия «разделяй и властвуй» позволяет, исходяиз этого, описать алгоритм построения выпуклой оболочки данногоГлава . Рекуррентные соотношения и сложность алгоритмовмножества n точек, сложность которого по общему числу операцийпри выборе n в качестве размера входа определяется соотношением(0,j kесли n = 1,l mT(n) =nn+T+ O(n) при n → ∞.T22От этого соотношения мы переходим к неравенству(0,j kесли n = 1,l mT(n) ¶nnT+T+ cn, если n > 1,22где c — некоторое неизвестное нам положительное число, — мы пользуемся здесь тем, что если g(n) = O(h(n)) и h(n) > 0 при n > 1, тоg(n) ¶ ch(n) для некоторой константы c и всех n > 1.Применяем теорему . (v + w = 2, log2 (v + w) = 1, d = 1). Это дает T(n) = O(n log n). Мы имеем, таким образом, еще один алгоритмпостроения выпуклой оболочки n заданных точек, по общему числуопераций имеющий сложность O(n log n).Теоремы о рекуррентных неравенствах в некоторых книгах формулируется иначе (см.
задачу ). Иногда в условии этой теоремыпредполагается, что исследуемая сложность является неубывающейфункцией от n. Перед тем как применять теорему в таком ее видек сложности конкретного алгоритма, необходимо доказывать неубывание этой сложности. Неубывание не является самоочевидным фактом для алгоритмов, построенных по стратегии «разделяй и властвуй». Например, для бинарного алгоритма вычисления an это не так:TRS (7) = 4, TRS (8) = 3. В теоремах . и . неубывание не предполагается.Еще одно замечание.
В § мы получали формулы и оценки длясложностей алгоритма бинарного поиска места элемента, сортировки фон Неймана и т. д. путем сравнения возникающих величин с последовательностью 2l , l = 0, 1, ...; этот прием во многом аналогичениспользованию соотношений вида (.), (.), но в том лишь частном случае, когда одно из чисел v, w равно нулю.§ .
Добавление нулейРяд алгоритмов целочисленной арифметики и теории матриц оказывается достаточным (без нанесения сколь-либо существенного ущерба идее алгоритма и его качеству) описать для случая, когда размерСм., например, [].§ . Добавление нулейвхода есть число вида 2k . При использовании стратегии «разделяйи властвуй» это облегчает и описание алгоритма, и анализ его сложности. С теоретической точки зрения для задачи умножения двух целых чисел a и b мы можем предполагать, что битовая длина каждогоиз данных чисел равна 2k , гдеk = max{⌈log2 λ(a)⌉, ⌈log2 λ(b)⌉},(.)так как всегда возможно добавить спереди любого из данных чиселнекоторое количество нулей.
Если речь идет об умножении квадратных матриц A и B произвольного порядка n, то мы можем добавитьк матрицам несколько нулевых строк и столбцов так, чтобы сделатьих порядки равными 2⌈log2 n⌉ :A 0B 0AB 0(.)0 00 00 0(нулями обозначены нулевые блоки соответствующего размера).Несмотря на переход от начальных данных к более громоздким, некоторые из алгоритмов, основанных на стратегии «разделяй и властвуй» и использующих этот переход, имеют существенно меньшуюсложность, чем наивные алгоритмы.Предложение ..
Пусть вещественная функция f натуральногоаргумента такова, что f (n) = f (2⌈log2 n⌉ ) для всех n ∈ N+ и¨u,если k = 0,kf (2 ) ¶wf (2k−1 ) + ϕ (2k ), если k > 0,при k ∈ N, где u, w — вещественные числа, причем u ¾ 0, w ¾ 1, а ϕ —неотрицательная функция, определенная для всех n ∈ N+ . Тогда привсех n ∈ N+ выполняется неравенство(u, l mесли n = 1,(.)f (n) ¶n⌈log2 n⌉+ ϕ (2), если n > 1.wf2Доказательство. Легко видеть, чтоl mmln= ⌈log2 n⌉ − 1.log22(.)l mnВ самом деле, если 2k−1 < n ¶ 2k , k > 1, то 2k−2 <¶ 2k−1 , т.
е. ес2ll mmnли ⌈log2 n⌉ = k, то log2= k − 1. Для случая n = 2⌈log2 n⌉ неравен2ство (.) выполнено по условию,для остальных случаев используемl mn= f (2⌈log2 ⌈n/2⌉⌉ ) = f (2⌈log2 n⌉−1 ).равенства f (n) = f (2⌈log2 n⌉ ), f2Глава . Рекуррентные соотношения и сложность алгоритмовТеорема .. Пусть вещественная функция f натурального аргумента такова, что f (n) = f (2⌈log2 n⌉ ) для всех n ∈ N+ и¨u,если k = 0,kf (2 ) ¶wf (2k−1 ) + c(2k )d , если k > 0,при k ∈ N, где u, d ¾ 0, c > 0, w ¾ 1. Тогда при рассмотрении f какфункции, определенной для всех n ∈ N+ , выполняются оценкиdO(n log n), если d = log2 w,df (n) = O(n ),если d > log2 w,log2 wO(n),если d < log2 w.Доказательство следует из предложения . и теоремы ..Подобно тому, как доказательство теоремы . было преобразовано в доказательство теоремы ., из приведенного выше доказательства мы можем получить доказательство следующей теоремыТеорема .. Пусть вещественная функция f натурального аргумента такова, что f (n) = f (2⌈log2 n⌉ ) для всех n ∈ N+ и¨u,если k = 0,kf (2 ) ¾wf (2k−1 ) + c(2k )d , если k > 0,где u, d ¾ 0, c > 0, w ¾ 1.
Тогда для функции f (n), при рассмотренииее как функции, определенной для всех n ∈ N+ , выполненоdΩ(n log n), если d = log2 w,log2 wf (n) = Ω(n),если d > log2 w,dΩ(n ),если d < log2 w.Перейдем к примерам.Пример . (умножение Карацубы). Пусть a и b — целые положительные числа битовой длины m = 2k . Положив l = 2k−1 , можемзаписатьa = e2l + f , b = g2l + h,где e, f , g, h — целые числа битовой длины l.
А. А. Карацубе принадлежит замечательное наблюдение, позволяющее вычислить произведение ab, выполнив всего три умножения чисел половинной длины,несколько сдвигов (домножений на 2m и 2l ) и несколько аддитивныхопераций над числами битовой длины ¶ 2m:ab = eg22l + ((e + f )(g + h) − eg − fh)2l + fh,(.)§ . Добавление нулейтогда как обычное раскрытие скобок в (e2l + f )(g2l + h) требует выполнения четырех таких умножения:ab = eg22l + (eh + fg)2l + fh.(.)Мы видим, что формула (.) использует произведения eg, fh,(e + f )(g + h), а формула (.) — произведения eg, eh, fg, fh.Небольшая проблема, которая выше была замаскирована словами «половинная длина», состоит в том, что битовая длина любогоиз чисел e + f , g + h, входящей в произведение (e + f )(g + h), можетоказаться равной l + 1, а не l.
Но еслиe + f = e1 2l + f1 ,g + h = g1 2l + h1 ,где e1 , g1 — однобитовые числа (0 или 1), то(e + f )(g + h) = e1 g1 22l + (e1 h1 + g1 f1 )2l + f1 h1 .(.)Произведение f1 h1 вычисляется рекурсивным обращением к алгоритму, произведения e1 g1 , e1 h1 , g1 f1 , как и все сложения и сдвиги, требуют O(l) операций.Равенство (.) и предположение, что m = 2k , приводят к рекурсивному алгоритму Карацубы умножения целых положительных чисел (будем обозначать этот алгоритм буквами KM: первая из этихбукв — начальная в фамилии автора алгоритма, вторая — в английском слове multiplication — умножение). Предположение m = 2k приводит к следующему соотношению для битовой сложности умножения Карацубы:(1, если m = 1,(.)TKM (m) ¶m+ cm, если m > 1,3TKM2где c — некоторая положительная константа.Умножение Карацубы при произвольном входе a, b ∈ N+ размера m = max{λ(a), λ(b)} предполагает, что сначала мы находим k == ⌈log2 m⌉, затем добавляем спереди каждого из a, b некоторое количество нулей так, чтобы битовая длина каждого из сомножителейстала равной 2k , а после этого используем рекурсивный алгоритм,основанный на (.).Мы можем применить теорему . (w = 3, d = 1), так как припроизвольном m ∈ N+ выполняется TKM (m) = TKM (2⌈log2 m⌉ ).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
