Лекции о сложности алгоритмов. С. А. Абрамов (1121249), страница 34
Текст из файла (страница 34)
В такихслучаях оказывается возможным найти явные формулы для сложности алгоритма. Асимптотические формулы иногда удается получитьнепосредственно из общего решения, не прибегая к вычислению значений входящих в него произвольных постоянных.С помощью рекуррентных уравнений мы получаем информациюо вычислительной сложности рекурсивного алгоритма. Правда, делоне всегда обстоит просто, — иногда возникают уравнения с переменными коэффициентами или нелинейные уравнения и неравенства,и об этом мы еще будем говорить. Тем не менее, сам метод исследования сложности рекурсивных алгоритмов с помощью рекуррентныхуравнений выглядит очень естественно.Задержимся на формулах (.), (.). Если бы построение множества 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). Это доказывает(.).Свойства (.), (.) дают нам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.Мы еще раз прервем рассмотрение примера . и сформулируемследующее предложение.§ . Об одном классе нелинейных рекуррентных соотношенийПредложение ..
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
