С.А. Абрамов - Лекции о сложности алгоритмов (pdf) (1123764), страница 33
Текст из файла (страница 33)
Это доказывает(.).Свойства (.), (.) дают намf (n) ¶ F(n) ¶ F(2⌈log2 n⌉ )(.)для n ¾ 1. Исследуем функцию t(k) = F(2k ), k = 0, 1, ... В силу (.)¨u,если k = 0,kF(2 ) =(v + w)F(2k−1 ) + ϕ (2k ), если k > 0,и, следовательно, t(k) удовлетворяет линейному рекуррентному уравнению (.). Отсюда и из (.) следует требуемое.Определение .. Рекуррентное уравнение (.), включающее всебя начальное условие t(0) = u, мы назовем уравнением, ассоциированным с рекуррентным неравенством (.).Если u, v, ϕ (n) удовлетворяют условиям, сформулированным впредложении ., то решение ассоциированного уравнения — неотрицательная функция (см.
задачу ).Глава . Рекуррентные соотношения и сложность алгоритмовПродолжение примера .. Уравнением, ассоциированным с (.),будет¨0,если k = 0,t(k) =(.)k2t(k − 1) + 2 − 1, если k > 0.Отвлекаясь временно от начального значения t(0) = 0, мы замечаем,что правая часть вt(k) − 2t(k − 1) = 2k − 1(.)является суммой квазиполиномов 2k и −1; первый из них, т. е. 2k ,интересен тем, что 2 является корнем характеристического уравнения λ − 2 = 0, и поэтому рекуррентное уравнение t(k) − 2t(k − 1) = 2kимеет частное решение вида p(k)2k , где p(k) — полином первой степени. Подстановка (p1 k + p0 )2k в рекуррентное уравнение дает(p1 k + p0 )2k − (p1 (k − 1) + p0 )2k = 2k ,откуда получаем, что p1 = 1, p0 — любое.
Итак, k2k является частным решением рекуррентного уравнения с правой частью 2k . Слагаемое −1 правой части исходного уравнения можно переписать в виде(−1) · 1k , единица не является корнем характеристического уравнения, поэтому рекуррентное уравнение t(k) − 2t(k) = −1 имеет в качестве частного решения некоторую константу, значение которой определяется без труда — это 1.Таким образом, любое решение рекуррентного уравнения (.)может быть записано в видеc2k + k2k + 1с некоторым конкретным c. Из условия t(0) = 0 находим c = −1 иt(k) = k2k − 2k + 1.(.)По предложению .TMS (n) ¶ ⌈log2 n⌉2⌈log2 n⌉ − 2⌈log2 n⌉ + 1 == (⌈log2 n⌉ − 1)2⌈log2 n⌉ + 1 ¶¶ log2 n · 2log2 n+1 + 1 == 2n log2 n + 1.Мы еще раз прервем рассмотрение примера . и сформулируемследующее предложение.§ .
Об одном классе нелинейных рекуррентных соотношенийПредложение .. Пусть вещественная функция 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) вместо выбора в (.) слагаемого,содержащего степень двойки с бо̀льшим показателем, мы выбираем§ . Асимптотические оценки решений рекуррентных неравенств то слагаемое, которое содержит степень двойки с меньшим показателем. Вместо предложения . пользуемся предложением ..Справедливость следующего предложения проверяется непосредственно.Предложение ..
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
