§ 24. Простейшие рекуррентные уравнения

161

Таким образом, z{n) = F_n+1 - 1. Отсюда следует ряд асимптотических формул:

z(n) = -j=0ⁿ⁺¹ + O(l), z(n) ~ -±=ф^п+1, z{n) = Q{<bⁿ) (24.6)

V5 V5

и т.д. Обратимся теперь к (24.2). Характеристическим уравнением здесь вновь является (24.4). Поскольку F_n+1 = с_гф^п + с₂ф^п, где с_ъс₂ — полиномы нулевой степени, то правая часть уравнения (24.2) явля­ется суммой двух квазиполиномов, и для нахождения интересующе­го нас решения может быть привлечен общий метод, в результате чего получится формула вида у{п) = р_г{п)ф^п + р₂{п)ф^п, где, в силу того, что ф и ф являются корнями кратности 1 характеристическо­го уравнения, а также того, что с_ъс₂ф0, степени полиномов р_г{п) и р₂{п) равны 1. Это показывает, что у{п) = С_гф^п+ С₂ф^п+ р_г{п)ф^п + + р₂{п)ф^п = q₁(n)ф^п + q₂{n)ф^п при соответствующем выборе полино­мов qi(n),q₂(n) первой степени. Можно было бы найти эти полино­мы, но даже не делая этого, а просто принимая во внимание, что степень q₁(n) равна 1, получаем

у(п) = в(пф"). (24.7)

Мы видим, что анализ сложности простейших рекурсивных алго­ритмов часто приводит к линейным рекуррентным уравнениям пер­вого или второго порядка с постоянными коэффициентами (однород­ным или с правыми частями в виде суммы квазиполиномов). В таких случаях оказывается возможным найти явные формулы для сложно­сти алгоритма. Асимптотические формулы иногда удается получить непосредственно из общего решения, не прибегая к вычислению зна­чений входящих в него произвольных постоянных.

С помощью рекуррентных уравнений мы получаем информацию о вычислительной сложности рекурсивного алгоритма. Правда, дело не всегда обстоит просто,—иногда возникают уравнения с перемен­ными коэффициентами или нелинейные уравнения и неравенства, и об этом мы еще будем говорить. Тем не менее, сам метод исследо­вания сложности рекурсивных алгоритмов с помощью рекуррентных уравнений выглядит очень естественно.

Задержимся на формулах (24.6), (24.7). Если бы построение мно­жества V_n при п > 2 разворачивалось не по алгоритму V_Rec, а несколь­ко иначе, то затрат было бы существенно меньше. Можно находить шаг за шагом множества V₁,V₂,V₃, ... до появления интересующего нас V_n, при этом каждое V_k, к = 3, 4,..., п, строится исходя из уже име­ющихся множеств V_k2 и У_кг. Или же можно организовать рекурсию

162 Глава 6. Рекуррентные соотношения и сложность алгоритмов

для вычисления пары Р_п = (V_n, V_n-₁) так, чтобы при вычислении Р_п исходя из Р_п-₁ множество V_n-₁ просто переходило бы из пары в пару. Будем использовать обозначения у*(п) и z*(n) для количества преоб­разований чисел и соответственно для количества объединений мно­жеств, затрачиваемых при нахождении (V_n,V_n-₁). При п>2 имеем y*(n) = y*(n-1)+F_n+F„-1. Перепишем уравнение в более удобном виде и добавим начальное значение:

y*(n)-y*(n-1) = F_n+1, (24.8)

у*(1) = 0. Аналогично,

z*(n)-z*(n-1) = 1, (24.9)

z*(1) = 0. Легко получаем z*(n) = n- 2 для п^2 и у*(п) = в(ф").

Причина избыточной сложности первого из рассмотренных алго­ритмов ясна. Построение V_n требует вычисления У_п-₁ и V_n-₂, а У_п-₁ в свою очередь потребует построения V_n-₂ и V_n-₃. Таким образом, да­же не прослеживая ход построений слишком далеко, мы видим, что требуются два независимых построения множества V_n-₂, при этом по­строение V_n-₂ по тем же причинам будет производиться не лучшим образом.

Пример 24.3. Достаточно ясно, что при к > 2 рекурсия вида

Y_n = U(Y_n-₁,...,Y_n-_k) (24.10)

(например, с заданными У₀,У₁,...,У_к-₁) заслуживает еще меньше до­верия, чем при к = 2, коль скоро эта рекурсия предписывает неза­висимое вычисление Y_n-1,Y_n-2, ...,Y_n-k; при этом не важно, являются ли Y_t числами, множествами или же какими-то другими объектами. Нахождение Y_n с помощью простейшего циклического алгоритма по­требует п-к + 1 обращений к U. Если при рекурсивном нахождении их требуется у(п), то

у(п) - у(п - 1) - ... - у(п - к) = 1, (24.11)

у(0) = у(1) = ... = у(к - 1) = 0. Можно найти асимптотику у(п), не решая полностью рекуррентного уравнения (24.11), и получить сле­дующее предложение.

Предложение 24.1. Пусть рекурсивный алгоритм организован по схеме (24.10), пусть к ^ 2 и пусть для получения значения функции U необходимы значения всех ее к аргументов. Тогда количество вычис­лений значений этой функции при нахождении Y_n есть Q(aⁿ_k), и а_к

удовлетворяет условию 2-^а_к<2, к = 2,3,