С.А. Абрамов - Лекции о сложности алгоритмов (pdf) (1123764), страница 32
Текст из файла (страница 32)
Рекуррентные соотношения и сложность алгоритмовметода решения линейных рекуррентных уравнений с постояннымикоэффициентами.Используя рекуррентные уравнения, мы можем определить количество y(n) преобразований чисел при построении множества Vnпо описанному алгоритму (каждое из этих преобразований состоит в приписывании справа к числу единицы или двойки). Мы можем также определить число z(n) выполняемых операций объединения множеств. Очевидно, имеет место уравнение y(n) = y(n − 1) ++ y(n − 2) + Fn + Fn−1 , которое мы перепишем в более удобном видеи добавим начальные значения:y(n) − y(n − 1) − y(n − 2) = Fn+1 ,(.)y(2) = y(1) = 0.
Аналогично, имеемz(n) − z(n − 1) − z(n − 2) = 1,(.)z(2) = z(1) = 0.Начнем со второго уравнения. Будем, как обычно, прибегатьк обозначениямppφ=1+ 5,2φ̃ =1− 5.2Непосредственно видно, что −1 является частным решением нашего рекуррентного уравнения (это частное решение можно получитьи общим методом: правая часть является квазиполиномом 1n , приэтом 1 не есть корень характеристического уравненияλ2 − λ − 1 = 0,(.)и, следовательно, существует частное решение вида c1n , где c — полином нулевой степени, т. е. константа; подстановка в (.) даетc = −1). Корнями уравнения (.) служат числа φ и φ̃ , входящиев формулу Бине, и общее решение уравнения (.) может быть записано в виде z(n) = C1 φ n + C2 φ̃ n − 1. Начальные условия z(2) = z(1) = 0приводят нас к системеpp1+ 51− 5C1 +C2 = 1,22p 2p 21+ 51− 5C1 +C2 = 1.22ПолучаемφC1 = p ,5φ̃C2 = − p .5(.)§ .
Простейшие рекуррентные уравненияТаким образом, z(n) = Fn+1 − 1. Отсюда следует ряд асимптотическихформул:15z(n) = p φ n+1 + O(1),15z(n) ∼ p φ n+1 ,z(n) = Θ(φ n )(.)и т. д. Обратимся теперь к (.). Характеристическим уравнениемздесь вновь является (.). Поскольку Fn+1 = c1 φ n + c2 φ̃ n , где c1 , c2 —полиномы нулевой степени, то правая часть уравнения (.) является суммой двух квазиполиномов, и для нахождения интересующего нас решения может быть привлечен общий метод, в результатечего получится формула вида y(n) = p1 (n)φ n + p2 (n)φ̃ n , где, в силутого, что φ и φ̃ являются корнями кратности 1 характеристического уравнения, а также того, что c1 , c2 6= 0, степени полиномов p1 (n)и p2 (n) равны 1. Это показывает, что y(n) = C1 φ n + C2 φ̃ n + p1 (n)φ n ++ p2 (n)φ̃ n = q1 (n)φ n + q2 (n)φ̃ n при соответствующем выборе полиномов q1 (n), q2 (n) первой степени.
Можно было бы найти эти полиномы, но даже не делая этого, а просто принимая во внимание, чтостепень q1 (n) равна 1, получаемy(n) = Θ(nφ n ).(.)Мы видим, что анализ сложности простейших рекурсивных алгоритмов часто приводит к линейным рекуррентным уравнениям первого или второго порядка с постоянными коэффициентами (однородным или с правыми частями в виде суммы квазиполиномов). В такихслучаях оказывается возможным найти явные формулы для сложности алгоритма. Асимптотические формулы иногда удается получитьнепосредственно из общего решения, не прибегая к вычислению значений входящих в него произвольных постоянных.С помощью рекуррентных уравнений мы получаем информациюо вычислительной сложности рекурсивного алгоритма.
Правда, делоне всегда обстоит просто, — иногда возникают уравнения с переменными коэффициентами или нелинейные уравнения и неравенства,и об этом мы еще будем говорить. Тем не менее, сам метод исследования сложности рекурсивных алгоритмов с помощью рекуррентныхуравнений выглядит очень естественно.Задержимся на формулах (.), (.).
Если бы построение множества Vn при n > 2 разворачивалось не по алгоритму VRec , а несколько иначе, то затрат было бы существенно меньше. Можно находитьшаг за шагом множества V1 , V2 , V3 , ... до появления интересующегонас Vn , при этом каждое Vk , k = 3, 4, ..., n, строится исходя из уже имеющихся множеств Vk−2 и Vk−1 . Или же можно организовать рекурсиюГлава . Рекуррентные соотношения и сложность алгоритмовдля вычисления пары Pn = (Vn , Vn−1 ) так, чтобы при вычислении Pnисходя из Pn−1 множество Vn−1 просто переходило бы из пары в пару.Будем использовать обозначения y ∗ (n) и z ∗ (n) для количества преобразований чисел и соответственно для количества объединений множеств, затрачиваемых при нахождении (Vn , Vn−1 ). При n > 2 имеемy ∗ (n) = y ∗ (n − 1) + Fn + Fn−1 .
Перепишем уравнение в более удобномвиде и добавим начальное значение:y ∗ (1) = 0. Аналогично,y ∗ (n) − y ∗ (n − 1) = Fn+1 ,(.)z ∗ (n) − z ∗ (n − 1) = 1,∗∗(.)∗nz (1) = 0. Легко получаем z (n) = n − 2 для n ¾ 2 и y (n) = Θ(φ ).Причина избыточной сложности первого из рассмотренных алгоритмов ясна. Построение Vn требует вычисления Vn−1 и Vn−2 , а Vn−1в свою очередь потребует построения Vn−2 и Vn−3 . Таким образом, даже не прослеживая ход построений слишком далеко, мы видим, чтотребуются два независимых построения множества Vn−2 , при этом построение Vn−2 по тем же причинам будет производиться не лучшимобразом.Пример ..
Достаточно ясно, что при k > 2 рекурсия видаYn = U(Yn−1 , ..., Yn−k )(.)(например, с заданными Y0 , Y1 , ..., Yk−1 ) заслуживает еще меньше доверия, чем при k = 2, коль скоро эта рекурсия предписывает независимое вычисление Yn−1 , Yn−2 , ..., Yn−k ; при этом не важно, являютсяли Yi числами, множествами или же какими-то другими объектами.Нахождение Yn с помощью простейшего циклического алгоритма потребует n − k + 1 обращений к U. Если при рекурсивном нахожденииих требуется y(n), тоy(n) − y(n − 1) − ... − y(n − k) = 1,(.)y(0) = y(1) = ... = y(k − 1) = 0. Можно найти асимптотику y(n), нерешая полностью рекуррентного уравнения (.), и получить следующее предложение.Предложение ..
Пусть рекурсивный алгоритм организован посхеме (.), пусть k ¾ 2 и пусть для получения значения функции Uнеобходимы значения всех ее k аргументов. Тогда количество вычислений значений этой функции при нахождении Yn есть Θ(αnk ), и αkудовлетворяет условию 2 −1¶ αk < 2, k = 2, 3, ...k§ . Об одном классе нелинейных рекуррентных соотношенийВ приложении H можно найти полное доказательство этого предложения.
Оно основывается на исследовании расположения на комплексной плоскости корней алгебраических уравненийλk − λk−1 − ... − λ − 1 = 0,k = 2, 3, ... Эти уравнения являются характеристическими для рекуррентных уравнений (.).§ . Об одном классе нелинейных рекуррентных соотношенийОдним из источников появления рекурсии в алгоритмах служит привлечение стратегии «разделяй и властвуй»: вычислительная задачас размером входа n разбивается на s > 1 одноименных задач, размер входа любой из которых примерно равен n/s («разделяй»); этизадачи решаются рекурсивно, т. е.
с применением этой же стратегии, а затем полученные решения соединяются в решение исходнойзадачи («властвуй»). Для входов маленьких размеров — как правило, 0 или 1 — задачи решаются каким-то простым способом, без рекурсии. При анализе сложности таких алгоритмов возникают специфические нелинейные рекуррентные соотношения в виде уравненийи неравенств. В общем случае такие соотношения довольно трудныдля решения, но для многих конкретных задач удается исследоватьсложность алгоритмов сведением рекуррентных соотношений к хорошо изученным линейным рекуррентным уравнениям первого порядкас постоянными коэффициентами и квазиполиномиальными правымичастями.Пример .. Обратимся к сортировке слияниями в ее рекурсивном варианте и исследуем ее сложность TMS (n) по числу сравнений(n — длина массива).
Функция TMS (n) подчиняется рекуррентномунеравенству(0, j kесли n = 1,l m(.)TMS (n) ¶nn+ TMS+ n − 1, если n > 1.TMS22В самом1 сортировка первыхj k деле, для любого массива длиныjn >knnегоэлементов потребует не более TMSсравнений (так как2j2 kn— это максимальное число сравнений, которое может поTMS2требоватьсярассматриваемой сортировке при работеj kl m с массивом длиnnны); аналогично, сортировка последнихэлементов потре22Глава . Рекуррентные соотношения и сложность алгоритмовl mnбует не более, чем TMSсравнений, а слияние потребует срав2j k l mnn+− 1 = n − 1.
В люнений в количестве, не превосходящем22j kn+бом, а значит, и в худшем случае потребуется не более TMS2l mn+ n − 1 сравнений.+ TMS2Рекуррентные неравенства, схожие с неравенством (.), характерны для многих алгоритмов, построенных на стратегии «разделяйи властвуй». Мы прервем на некоторое время рассмотрение этогопримера и обсудим общую ситуацию с неравенствами возникающего типа.Предложение .. Пусть вещественная функция f натуральногоаргумента удовлетворяет неравенству(u, j kесли n = 1,l mf (n) ¶(.)nnvf+ wf+ ϕ (n), если n > 1,22где u, v, w — неотрицательные вещественные числа, причем v + w ¾ 1,а функция ϕ — неотрицательная неубывающая. Тогдаf (n) ¶ t(⌈log2 n⌉),где¨t(k) =(.)u,если k = 0,(v + w)t(k − 1) + ϕ (2k ), если k > 0.(.)Доказательство. Установим прежде всего, что вещественнаяфункция F натурального аргумента, удовлетворяющая равенству(u, j kесли n = 1,l m(.)F(n) =nn+ wF+ ϕ (n), если n > 1,vF22является неубывающей, т.
е. при n ¾ 2 выполненоF(n) ¾ F(n − 1).(.)Проведем индукцию по n. При n = 2 неравенство выполнено, так какF(2) = (v + w)u + ϕ (2) ¾ u = F(1).Пусть n > 2 и неравенство (.) выполнено для 2, 3, ..., n − 1; докажем, что тогда оно верно и для n. Воспользуемся тем, что при n > 2j k jkl m lmnn−1nn−1n>¾¾ 1, n >¾¾ 1.2222§ . Об одном классе нелинейных рекуррентных соотношенийИмеемj kF(n) = vFn2l m+ wFn2j¾ vF+ ϕ (n) ¾klmn−1n−1+ wF+ ϕ (n − 1) = F(n − 1).22Неравенство (.) доказано.Аналогичным образом по индукции докажем, чтоf (n) ¶ F(n)(.)для n ¾ 1. Очевидно, f (1) ¶ u = F(1). Пусть n > 1 и неравенство (.)выполнено для 1, 2, ..., n − 1; докажем, что тогда оно верно и для n.В силу (.) мы имеем при n > 1j kl mnnf (n) ¶ vf+ wf+ ϕ (n),(.)22j kl mnnи так как при n > 1 выполняются неравенства¶n−1 и¶22¶ n − 1, то по предположению индукцииj kl mj kl mnnnnvf+ wf+ ϕ (n) ¶ vF+ wF+ ϕ (n). (.)2222Правая часть последнего неравенства есть F(n).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
