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

, mk (∑mi =1i= d ). Аналогично дифференциальным уравнениям, вслучае простого корня (кратность единица) будем иметь просто константу, в случае кратного37корня появляется многочлен (в общем случае, константу тоже можно рассматривать какмногочлен нулевой степени). Итого, общее решение однородного рекуррентногосоотношения будет иметь вид:∑ (Cki ,0i =1)+ Ci ,1n + ... + Ci , mi −1n mi −1 λinРассмотрим теперь неоднородное рекуррентное соотношение. Когда в правой части стоитквазиполином (выражение вида p(n) µ n , где p(n) — полином) или сумма квазиполиномов,то в линейной алгебре доказывается, что частное решение в этом случае, тоже будетквазиполиномом.

Для нахождения частного решения (как и в случае дифференциальныхуравнений) смотрим, сколько раз µ встречается среди корней характеристическогоуравнения. Пусть среди корней характеристического уравнения µ встречается l раз, тогдачастным решением будет квазиполином q (n) µ n , где deg q(n) = l + deg p(n) .Если в правой части стоит сумма квазиполиномов, то для построения частного решениянужно получить квазиполином для каждого слагаемого и просуммировать.Таким образом, для (*) характеристическим уравнением будет следующее:λ2 − λ − 1 = 01+ 51− 5 ~= φ и λ2 == φ .

Исходя из этого, получаем, что22общем решение однородного рекуррентного соотношения будет иметь вид:~C1φ n + C2φ nкорнями которого будут λ1 =В правой части стоит «1», но никто не мешает рассматривать её как 1n , т.е. она являетсяквазиполиномом ( µ = 1 ; p(n) = 1 ). 1 не встречается среди корней характеристическогоуравнения, поэтому частное решение можно искать в виде константы, откуда получаем, что− 1 будет являться частным решением (*).

Общее решение неоднородного соотношениебудет складываться из общего решения однородного и частного решения неоднородного:~z (n) = C1φ n + C2φ n − 1Из начальных условий ( z (1) = z (2) = 0 ), находим константы: C1 =()11, C2 = −. Таким551 n1 n ~nφ − φ −1 =φ + O(1) . Можно выписать более простую (и более55грубую) оценку: z (n) = Θ φ n .образом z (n) =( )Обратимся к соотношению для y (n) : очевидно, что −~n1φ~= φ и по формуле Бене получаем,что правая часть Fn +1 = C1φ + C2φ , где C1 и C2 — полиномы нулевой степени, т.е. имеетвид суммы двух квазиполиномов, причем имеет место совпадение с корнямихарактеристического уравнения.

Это указывает на то, что наше соотношение будет обладать~частным решением следующего вида: p1 (n)φ n + p2 (n)φ n , где p1 (n) и p2 (n) — полиномы 1-йстепени.nОбщее решение неоднородного соотношения будет иметь вид:~~~y (n) = C1φ n + C2φ n + p1 (n)φ n + p2 (n)φ n = q1 (n)φ n + q2 (n)φ n ,38где q1 (n) и q2 (n) — полиномы, имеющие первую степень. Их можно найти, но в данномслучае это не нужно, т.к.

нам нужна оценка для y (n) . Для y (n) будет верна следующаяоценка: y (n) = Θ(nφ n ) . Если нужны более точные оценки, то их можно вычислить, найдяточные представления для q1 (n) и q2 (n) .Отметим, что представленный алгоритм вычисления Vn не является эффективным.Действительно, Vn вычисляется, исходя из Vn −1 и Vn − 2 .

Vn −1 , в свою очередь, вычисляется,исходя из Vn − 2 и Vn − 3 . Но Vn − 2 и в том и в другом случае будут вычисляться независимо (ужтакой алгоритм). Поэтому напрашивается следующая модернизация: нужно вычислятьмножества парами: (Vn , Vn −1 ) , (Vn −1 , Vn − 2 ) , …, где Vn −1 просто переходит. Тогда, для числаопераций над числами получим такое соотношение:y * (n) − y * (n − 1) = Fn +1y * (1) = 0Характеристическое уравнение такого соотношения будет уравнением первой степени,имеющее единственный корень λ = 1 ⇒ y * (n) = Θ(φ n ) .Для числа объединений получаем следующее рекуррентное соотношение:z * (n) − z * (n − 1) = 1z (1) = 0*⇒ z * ( n) = n − 2Рассмотрим ещё более «неприятную» рекурсию:Yn = U (Yn −1 , Yn − 2 , ...

, Yn − k )Сколько раз при обращении к Yn нужно будет обратиться к U ? Возникает такоерекуррентное соотношение:y (n) − y (n − 1) − ... − y (n − k ) = 1y (0) = ... = y (k − 1) = 0потому что можно считать, что Y0 , Y1 , ... , Yk −1 нам известны.Чтобы разобраться, как решение будет себя вести, надо исследовать характеристическоеуравнение:λk − λk −1 − ...

− λ − 1 = 0Может быть показано следующее: все корни, кроме одного, этого характеристическогоуравнения лежат внутри единичного круга на комплексной плоскости, а для последнегокорня верно 1 < λk < 2 , причём при k → ∞ λk → 2 . Таким образом, когда k → ∞ для( )сложности получаем оценку Θ 2n .Стратегия «разделяй и властвуй» заключается в следующем: пусть имеется задача, размервхода равен n; разбиваем исходную задачу на несколько подзадач, размеры хода которыхnбудут меньше n (если c задач, то размеры входас соответствующим округлением). Вcслучае размера входа n = 0 или n = 1 , предполагаем, что решение задачи известно.Обратимся к какому-нибудь известному алгоритму, чтобы увидеть, как всё это работает.

Дляпримера рассмотрим алгоритм сортировки слияниями (MS = merged sort): пусть дан массив39⎢n⎥ ⎡n⎤x1 , ... , xn , разделяем его на две части длинами ⎢ ⎥ и ⎢ ⎥ , упорядочиваем полученные части⎣2⎦ ⎢2⎥(применяя алгоритм рекурсивно) и сливаем. Если длина массива равна 1, то ничего делать ненадо.Если мы попробуем исследовать сложность (в худшем случае) этого алгоритма по числусравнений, то⎧0, n = 1⎪TMS (n) ≤ ⎨ ⎛ ⎢ n ⎥ ⎞⎛⎡n⎤⎞−1 , n > 1⎪TMS ⎜⎜ ⎢ 2 ⎥ ⎟⎟ + TMS ⎜⎜ ⎢ 2 ⎥ ⎟⎟ + n{⎝ ⎢ ⎥ ⎠ на слияние⎩ ⎝⎣ ⎦⎠Пока не знаем, что равенство достигается, поэтому ставим ≤ .Разные книги по-разному показывают, как работать с этим соотношением.

Мы сведём его крекуррентному соотношению с постоянными коэффициентами.Предложение. Пусть функция f : N → R такая, что⎧u , n = 1⎪f ( n) ≤ ⎨ ⎛ ⎢ n ⎥ ⎞⎛⎢n⎥⎞+vfwf⎜⎜ ⎢ ⎥ ⎟⎟ + ϕ (n), n > 1,⎟⎜⎟⎜⎪⎢⎣ 2 ⎥⎦⎝⎣2⎦⎠⎠⎝⎩где u, v, w — целые неотрицательные числа и v, w не равны нулю одновременно, функцияϕ : N → R неотрицательная и неубывающая. Тогда f (n) ≤ t (⎡log 2 n ⎤) , где t (n) — решениерекуррентного уравнения⎧u , k = 0t (k ) = ⎨k⎩(v + w) ⋅ t (k − 1) + ϕ (2 ), k > 0⎧u , n = 1⎪Доказательство: Введём F (n) = ⎨ ⎛ ⎢ n ⎥ ⎞(то же, что и f (n) , но с⎛⎡n⎤⎞ϕ+>+(),1vFwFnn⎟⎜⎟⎜⎟⎜⎟⎜⎪⎢ ⎥⎢ ⎥⎝⎢2⎥⎠⎩ ⎝⎣2⎦⎠«=»). Можно доказать, что F (n) является неубывающей, т.е.∀n ≥ 2 ⇒ F (n) ≥ F (n − 1)(*)Доказательство этого факта проведём по индукции: для n = 2 имеем:F (1)}F (2) = (v + w) u + ϕ (2) ≥ u = F (1)123≠0⎢ n ⎥ ⎢ n − 1⎥⎡ n ⎤ ⎡ n − 1⎤≥ 1, n > ⎢ ⎥ ≥ ⎢≥1Если неравенство (*) выполнено для 2,3,…, n − 1 , то n > ⎢ ⎥ ≥ ⎢⎥⎣2⎦ ⎣ 2 ⎦⎢ 2 ⎥ ⎢ 2 ⎥⎥⎛ ⎢n⎥⎞⎛⎡n⎤⎞⎛ ⎢ n − 1⎥ ⎞⎛ ⎡ n − 1⎤ ⎞(n − 1) = F (n − 1)⇒ F (n) = vF ⎜⎜ ⎢ ⎥ ⎟⎟ + wF ⎜⎜ ⎢ ⎥ ⎟⎟ + ϕ (n) ≥ vF ⎜⎜ ⎢⎟⎟ + wF ⎜⎜ ⎢⎥⎥ ⎟⎟ + ϕ4243⎝ ⎣2⎦⎠⎝⎢2⎥⎠⎝⎣ 2 ⎦⎠⎝⎢ 2 ⎥⎠ 1не убывает()Аналогично доказывается индукцией, что f (n) ≤ F (n) ⇒ f (n) ≤ F (n) ≤ F 2 ⎡log2 n ⎤ .⎧u , k = 0F 2k = ⎨k −1k⎩(v + w) F 2 + ϕ 2 , k ≥ 1( )( ) ( )40т.е.

t (k ) = F (2 k ) , и предложение доказано.Теперь мы можем вернуться к алгоритму сортировки слияниями. В этом случае для t (k )имеем следующее рекуррентное уравнение:⎧0, k = 0t (k ) = ⎨k⎩2t (k − 1) + 2 − 1, k > 0Если его записать в более привычном для рекуррентных уравнений виде, то получимt (k ) − 2t (k − 1) = 2 k − 1t (0) = 0Корнем соответствующего характеристического уравнения будет λ = 2 . Правая часть, всвою очередь, содержит слагаемое 2k , поэтому частным решением будет p (k )2 k , гдеdeg p(k ) = 1 . «1» не является корнем характеристического уравнения, и вклад этогослагаемого будет весьма скромным.

В итоге, общее решение рекуррентного соотношениябудет иметь вид t (k ) = c1k 2 k + c2 2 k + c3 . Определив константы из начальных условий,получим: t (k ) = k 2 k − 2 k + 1TMS (n) = O(n log n) .⇒TMS (n) ≤ ⎡log 2 n ⎤2 ⎡log2 n ⎤ − 2 ⎡log2 n ⎤ + 1 ≤ 2n log 2 n + 1⇒Задержимся на некоторое время всём этом. Чувствуется, что для асимптотических оценок необязательно решать рекуррентное соотношение до конца.

Но если мы будем удовлетворятьасимптотическим верхним оценкам, то всего этого делать не нужно.Определение. Рекуррентное соотношение, которое сразу следует из условий, будемназывать ассоциированным.Если t (k ) = O(ψ (k ) ) , то f (k ) (из предложения) представляет собой f (n) = O(ψ (⎡log 2 n ⎤)) .Если дополнительно ψ такая, что ψ (n + 1) = O(ψ (n) ) (ψ растёт не слишком быстро), то дляf (n) можно написать f (n) = O(ψ (log 2 n )) .Возвращаясь к примеру с алгоритмом сортировки слияниями, замечаем что λ = 2 являетсякорнем характеристического уравнения, p (k )2 k , где deg p(k ) = 1 , является частнымрешением, а остальные слагаемые решения не будут по скорости роста дотягивать до него⇒ t (k ) = Θ(k 2 k ) .Упомянем следующее: мы нашли оценку сверху для алгоритма MS ( TMS ≤ 2n log 2 n + 1 ), нотщательный (кропотливый) анализ предполагает дополнительно нахождение оценки снизу.Для алгоритмов сортировки мы уже знаем, что оценка Ω(n log n) имеет место, поэтом вданном конкретном примере мы можем остановиться.Можно рассмотреть оценку для TMS снизу, т.е.

рассмотреть аналогичное рекуррентноенеравенство с ≥ . В этом случае будет справедливо предложение, аналогичное доказанному,за исключением того, что в этом случае 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 , ...