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

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 15)

, n — произведение всех модулей, кроме i-го, тогда gi ⊥ ki (взаимно просты) всилу того, что ki взаимно простые ⇒ по расширенному алгоритму Евклида найдём hinтакие, что hi g i ≡ 1(mod ki ) . Тогда можно положить f = ∑ bi gi hi .i =147. Найти оценки сложностей, если для них выполняются следующие рекуррентныесоотношения:⎛⎢n⎥⎞1) T (n) = T ⎜⎜ ⎢ ⎥ ⎟⎟ + log 2 n⎝⎣2⎦⎠⎛ ⎢n⎥⎞2) T (n) = 2T ⎜⎜ ⎢ ⎥ ⎟⎟ + n log 2 n⎝ ⎣2⎦⎠⎛⎢n⎥⎞3) T (n) = 2T ⎜⎜ ⎢ ⎥ ⎟⎟ + n 2⎝⎣2⎦⎠Решение. 1) используя предложение (стр. 40) получаем ассоциированное уравнение⎧0, k = 0t (k ) = ⎨⎩t (k − 1) + k , k > 0k (k + 1)решением которого будет t (k ) =⇒2⎣log 2 n⎦(⎣log 2 n⎦ + 1) ≤ T (n) ≤ ⎡log 2 n⎤(⎡log 2 n⎤ + 1) ⇒ T (n) = Θ(log 2 n ) .222) используя предложение (стр.

40) получаем ассоциированное уравнение⎧0, k = 0⎧t (k ) − 2 ⋅ t (k − 1) = k ⋅ 2 k⇔ ⎨t (k ) = ⎨k⎩2 ⋅ t (k − 1) + k ⋅ 2 , k > 0⎩t (0) = 067Характеристическим уравнением будет λ − 2 = 0 ⇒ λ = 2 поэтому общим решениемоднородного рекуррентного уравнения будет t о.о. (k ) = C ⋅ 2 k . Частное решениенеоднородного рекуррентного уравнения будем искать в виде t ч.н.

(k ) = k r p(k ) ⋅ 2k , где rсоответствует количеству совпадений основания степени из правой части ( k ⋅ 2k ),которое в нашем случае равно 2, с корнями характеристического уравнения. В нашемслучае r = 1 . Степень многочлена p(k ) совпадает со степенью многочлена из правойчасти, в нашем случае deg p(k ) = deg k = 1 , т.е.

p(k ) = ak + b где a и b — константы,подлежат определению. Таким образом, частное решение будем искать в видеt ч.н. (k ) = k (ak + b) ⋅ 2 k . Подставим его исходное уравнение:k (ak + b) ⋅ 2 k − 2 ⋅ (k − 1)(a(k − 1) + b ) ⋅ 2k −1 = k ⋅ 2k ⇔ ak 2 + bk − ak 2 + ak − bk + ak − a + b = k⎧a = 1 2k 1 : ⎧2 a = 1⇔ 2ak − a + b = k ⇒⇒ t ч.н. (k ) = k (k + 1) ⋅ 2k −1⇔ ⎨⎨0k : ⎩− a + b = 0⎩b = 1 2Общее решение неоднородного рекуррентного уравнения будет складываться изобщего решения однородного и частного неоднородного: t (k ) = t о.о. (k ) + t ч.н. (k ) ⇒t (k ) = C ⋅ 2 k + k (k + 1) ⋅ 2 k −1 .

Из начальных условий определяем C: t (0) = 0 ⇒ C = 0 ⇒t (k ) = k (k + 1) ⋅ 2k −1 . Откуда для сложности, согласно предложению, получаем оценку:⎣log 2 n⎦(1 + ⎣log 2 n⎦) ⋅ 2 ⎣log2 n ⎦ ≤ T (n) ≤ ⎡log 2 n⎤(1 + ⎡log 2 n⎤) ⋅ 2 ⎡log2 n ⎤ ⇒ T (n) = Θ(n log 2 n ).223) ассоциированное уравнение⎧t (k ) − 2 ⋅ t (k − 1) = 2 2 k⎨⎩t (0) = 0Корнем характеристического уравнения будет λ = 2⇒t о.о. (k ) = C ⋅ 2 k .

λ = 2 несовпадает с основанием степени в правой части: 2 2 k = (22 ) = 4 k , поэтому частноерешение будем искать в виде t ч.н. (k ) = p(k ) ⋅ 4k , где deg p(k ) = 0 ⇔ p(k ) = a , т.е.t ч.н. (k ) = a ⋅ 4k . Для определения константы a, подставляем частное решение в исходноеуравнение:aa ⋅ 4 k − 2a ⋅ 4 k −1 = 4 k ⇔ a − = 1 ⇒ a = 2 ⇒ t ч.н. (k ) = 2 ⋅ 4 k = 2 2 k +12Общим решением рекуррентного уравнения будет t (k ) = C ⋅ 2 k + 22 k +1 . Из начальногоусловия получаем: t (0) = 0 ⇒ C + 2 = 0 ⇒ C = −2 ⇒ t (k ) = 2 2 k +1 − 2 k +1 . Поэтому длясложности получаем оценку: t (⎣log 2 n ⎦) ≤ T (n) ≤ t (⎡log 2 n ⎤) ⇔k()()2 ⋅ 2 ⎣log2 n ⎦ − 2 ⋅ 2 ⎣log2 n ⎦ ≤ T (n) ≤ 2 ⋅ 2 ⎡log2 n ⎤ − 2 ⋅ 2 ⎡log2 n ⎤ ⇒ T (n) = Θ(n 2 ) .2682.

Характеристики

Список файлов лекций