Лекции о сложности алгоритмов. С. А. Абрамов (1121249), страница 35
Текст из файла (страница 35)
Пусть вещественная функция f натуральногоаргумента удовлетворяет неравенству(u, j kесли n = 1,l m(.)f (n) ¾nn+ wf+ ϕ (n), если n > 1,vf22где u, v, w — неотрицательные вещественные числа, причем v + w ¾ 1,а функция ϕ — неотрицательная неубывающая. Тогдаf (n) ¾ t(⌊log2 n⌋),(.)где t — решение рекуррентного уравнения (.).Доказательство получается заменой знака ¶ на ¾ в (.), (.)и (.), а также переходом от (.) кf (n) ¾ F(n) ¾ F(2⌊log2 n⌋ ).Сохраняя введенную терминологию, рекуррентное уравнение(.) будем называть ассоциированным с рекуррентным неравенством (.).Если же возникает соотношение со знаком = вместо ¾ или ¶, томы можем рассматривать его как систему двух рекуррентных неравенств (.), (.).
Тогда получим оценкиt(⌊log2 n⌋) ¶ f (n) ¶ t(⌈log2 n⌉).Завершим рассмотрение примера .. Можно доказать (см. задачу ), что для сложности по числу сравнений рекурсивной сортировки слияниями выполнено(0, j kесли n = 1,l mTMS (n) =(.)nnTMS+ TMS+ n − 1, если n > 1,22и прийти к справедливым для всех n оценкам(⌊log2 n⌋ − 1)2⌊log2 n⌋ + 1 ¶ TMS (n) ¶ (⌈log2 n⌉ − 1)2⌈log2 n⌉ + 1.(.)Для исследования сложности TeMS (n) рекурсивной сортировки слияниями по числу перемещений рассмотрим рекуррентное уравнение(0, j kесли n = 1,l m(.)TeMS (n) =nn+ TeMS+ n, если n > 1TeMS22Глава .
Рекуррентные соотношения и сложность алгоритмовj k l mnn(при слиянии массивов, содержащих соответственноиэле22ментов, требуется ровно n перемещений элементов). Решением ассоциированного уравнения¨0,если k = 0,t(k) =2t(k − 1) + 2k , если k > 0,является k2k , что дает нам⌊log2 n⌋2⌊log2 n⌋ ¶ TeMS (n) ¶ ⌈log2 n⌉2⌈log2 n⌉ .(.)Пространственная сложность этой сортировки есть Ω(n), ибо слияние упорядоченных массивов выполняется с получением результатана новом месте.
(Дополнительно к этому будет использоваться стекотложенных заданий.) Рассмотрение примера . закончено.Интересно посмотреть на результаты применения разобранногометода на каком-нибудь примере, для которого мы знаем точное значение сложности алгоритма, — сколь далеки будут получаемые оценки от известного точного значения?Пример .. Вернемся к бинарному алгоритму вычисления an(пример .), который можно легко описать рекурсивно.
Для егосложности по числу умножений имеем(0, j kесли n = 1,(.)TRS (n) ¶n+ 2, если n > 1,TRS2и(TRS (n) ¾0, j kесли n = 1,n+ 1, если n > 1.TRS(.)2Соответствующими ассоциированными уравнениями будут¨0,если k = 0,t(k) =t(k − 1) + 2, если k > 1,и¨t(k) =0,если k = 0,t(k − 1) + 1, если k > 1,их решения суть 2k и k. Отсюда⌊log2 n⌋ ¶ TRS (n) ¶ 2⌈log2 n⌉.(.)Эти оценки не сильно расходятся с точной формулой TRS (n) = λ(n) ++ λ∗ (n) − 2.§ . Асимптотические оценки решений рекуррентных неравенств § .
Асимптотические оценки решений рекуррентныхнеравенствРассмотренный метод оценивания решений рекуррентных неравенств (.), (.) приводит к достаточно точным оценкам, нотребует многоэтапной работы. Часто бывает достаточно получитьописание роста решения в виде простой асимптотической оценки.В § мы получили оценку (.), указав при этом, что для ее выводане нужно определять численные значения коэффициентов, входящихв соответствующее частное решение ассоциированного рекуррентного уравнения. Этот путь приводит к ряду общих теорем. Для нихв разных литературных источниках используются синонимичные названия «теорема о рекуррентном неравенстве», «основная теоремао рекуррентных оценках» и т.
д. Мы приведем две теоремы такогорода.Теорема . (о рекуррентном неравенстве, случай ¶). Пустьнеотрицательная вещественная функция f натурального аргументаудовлетворяет неравенству(u, j kесли n = 1,l m(.)f (n) ¶nnd+ wf+ cn , если n > 1,vf22где u, v, w, d — неотрицательные вещественные числа, причем v + w ¾¾ 1; c — положительное вещественное число. Тогдаdесли d = log2 (v + w),O(n log n),f (n) = O(nd ),(.)если d > log2 (v + w),log2 (v +w)O(n), если d < log2 (v + w).Доказательство.
Решение ассоциированного уравнения¨u,если k = 0,t(k) =d k(v + w)t(k − 1) + c(2 ) , если k > 0,имеет видt(k) = c0(v + w)k + (c1 k + c2 )(2d )k = c0 (2log2 (v +w) )k + (c1 k + c2 )(2d )k(.)с некоторыми конкретными c0 , c1 , c2 , причем c1 6= 0, если и только если 2d = v + w, или, что то же самое, если d = log2 (v + w). Рассмотримраздельно три случая.В литературе на английском языке — «master theorem» (мастер-теорема).Глава . Рекуррентные соотношения и сложность алгоритмовСлучай d = log2 (v + w).
Имеем t(k) = (c1 k + (c0 + c2 ))(2d )k . Для достаточно больших значений k выполняетсяt(k) < Ck(2d )k = Ck(2k )d ,где C — некоторое положительное число. Используя предложение .,заключаем, чтоf (n) < C ⌈log2 n⌉(2⌈log2 n⌉ )d .Это дает f (n) = O(nd log n).Случай d > log2 (v + w). Имеем t(k) = c0 (v + w)k + c2 (2d )k .
Для достаточно больших значений k будем иметьt(k) < C(2d )k = C(2k )d ,где C — некоторое положительное число. Аналогично предыдущемуслучаю с помощью предложения . получаем f (n) = O(nd ).Случай d < log2 (v + w). Вновь имеем t(k) = c0 (v + w)k + c2 (2d )k , нотеперь для достаточно больших значений k будем иметьt(k) < C(v + w)k = C(2log2 (v +w) )k = C(2k )log2 (v +w) ,где C — некоторое положительное число. С помощью предложения. приходим к оценке f (n) = O(nlog2 (v +w) ).Похожая теорема может быть доказана и для случая неравенствасо знаком ¾ вместо знака ¶.Теорема . (о рекуррентном неравенстве, случай ¾). Пустьвещественная функция f (n) натурального аргумента удовлетворяетнеравенству(u, j kесли n = 1,l mf (n) ¾nndvf+ wf+ cn , если n > 1,22где u, v, w, d — неотрицательные вещественные числа, причем v + w ¾¾ 1; c — положительное вещественное число.
Тогдаdесли d = log2 (v + w),Ω(n log n),log2 (v +w)f (n) = Ω(n(.)), если d > log2 (v + w),Ω(nd ),если d < log2 (v + w).Доказательство отличается от доказательства теоремы . лишьтем, что в случаях d 6= log2 (v + w) вместо выбора в (.) слагаемого,содержащего степень двойки с бо̀льшим показателем, мы выбираем§ . Асимптотические оценки решений рекуррентных неравенств то слагаемое, которое содержит степень двойки с меньшим показателем. Вместо предложения . пользуемся предложением ..Справедливость следующего предложения проверяется непосредственно.Предложение .. Если в условиях теорем . и . предположить, что 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 равно нулю.§ . Добавление нулейРяд алгоритмов целочисленной арифметики и теории матриц оказывается достаточным (без нанесения сколь-либо существенного ущерба идее алгоритма и его качеству) описать для случая, когда размерСм., например, [].§ .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
