На этом шаге мы рассмотрим преобразования дробных аргументов рекурсивной функции.

Общий метод вывода формулы для рекуррентных соотношений применим лишь тогда, когда аргументы их T-членов представляют собой разности вида n - b, где b - некоторая целочисленная константа. Однако в отдельных случаях эту задачу можно решить, когда аргументы T-членов представляют собой дроби вида n/b, где b - некоторая целочисленная константа. Ключевая идея здесь заключается в предположении, что n - это степень b, и последующем преобразовании дроби в разность путём замены n = bk.

Рассмотрим рекуррентное соотношение (3.30) с рекурсивным условием

    T(n) = 2T(n/2) + 1,

предположив, что n - степень двух. Поскольку аргумент T-члена в правой части - n/2, необходимо произвести замену n = 2^k, чтобы получить:

    T(2^k) = 2T(2^k/2) + 1 = 2T(2^k-1) + 1.

В этом новом определении T(2^k) есть функция k. Поэтому её можно заменить на t(k) следующим образом:

    t(k) = 2t(k - 1) + 1,

а такое рекуррентное соотношение можно решить общим методом для разностных уравнений. То есть сначала привести его к виду

    t(k) - 2t(k - 1) = 1 * 1ⁿ

и записать его характеристический полином

    (x - 2)(x - 1).

Тогда сама функция должна иметь следующий вид:

    t(k) = С₁ + С₂2^k       .    (3.43)

Выполнив обратную замену, получаем общее решение рекуррентного соотношения от исходной переменной n:

    T(n) = С₁ + С₂n     .               (3.44)

Последний шаг - определение констант С₁ и С₂. Их можно найти из (3.43) или из (3.44). Для T мы можем использовать начальные условия T(1) = 1 и T(2) = 3. Аналогичные начальные условия для t: t(0) = T(2⁰) = T(1) = 1 и t(1) = T(2¹) = T(2) = 3. В любом случае, система линейных уравнений будет иметь вид:

    C₁ + C₂ = 1 = T(1) = t(0)
    C₁ + 2C₂ = 3 = T(2) = t(1)

Её решение: C₁ = -1 и C₂ = 2, а формулой для T(n) будет:

    T(n) = 2n - 1 ∈ Θ(n).

В следующем рекурсивном определении

        1,               если n = 1
T (n) = 
        2T(n/4) + log₂n, если n > 1,

можно предположить, что аргументом рекурсивной функции T будет степень четырёх. В этом случае замена переменной n = 4k приводит к

    T(4^k) = 2T(4^k/4) + log₂4^k = 2T(4^k-1) + k log₂ 4 = 2T(4^k-1) + 2k.

Следующий шаг - замена t(k) = T(4^k):

    t(k) = 2t(k - 1) + 2k.

Мы назовём эту операцию "заменой функции", чтобы подчеркнуть, что замена касается только T-членов (t-членами) и не влияет на все остальные члены (в данном случае - 2k). Приводим рекуррентное соотношение к каноническому виду

    t(k) - 2t(k - 1) = 2k * 1^k,

характеристический полином которого -

    (х - 2)(х - 1)².

Таким образом, формула для этого рекуррентного соотношения:

    t(k) = C₁2^k + C₂ + C₃k.

Чтобы вернуться к функции T, нужно произвести обратную замену k = log₄ n. Однако нам необходимо выражение для 2k. Заметим, что n = 4^k = (2 * 2)^k = (2²)^k = (2^k)², поэтому 2^k = √n, что даёт:

    T(n) = C₁√n + C₂ + C₃ log₄ n.

Наконец, исходя из начального условия T(1) = 1, можно вычислить T(4) = 2T(1) + log₂ 4 = 4 и T(16) = 2T(4) + log₂ 16 = 12, что позволяет нам найти константы C_i из решения следующей системы линейных уравнений:

    C₁ + C₂ = 1 = T(1)
    2C₁ + C₂ + C₃ = 4 = T(4)
    4C₁ + C₂ + 2C₃ = 12 = T(16).

Её решение: C₁ = 5, C₂ = -4 и C₃ = -2, а формула для T(n):

    T(n) = 5√n - 4 - 2 log₄ n ∈ Θ(n^1/2).

Если аргумент T в рекурсивном выражении - квадратный корень, можно воспользоваться заменой n = 2^(2k). Рассмотрим следующее рекуррентное соотношение:

    T(n) = 2T(√n) + log₂ n,       (3.45)

где T(2) = 1 и n = 2^(2k) (заметим, что 2^(2k) ≠ 4^k). Это последнее ограничение для n гарантирует, что рекурсивная процедура завершится при начальном условии для n = 2. После замены переменной получим:

    T(2^(2k)) = 2T(2^(2k/2)) + log₂ 2^(2k) = 2T(2^(2k-1)) + 2^k,

а после замены функции t(k) = T(2^(2k)) рекуррентное соотношение принимает вид

    t(k) = t(k - 1) + 2^k,

характеристический полином которого

    (х - 2)(х - 2).

Поэтому новое рекуррентное соотношение будет иметь вид:

    t(k) = C₁2^k + C₂k2^k.

Для отмены замены переменной нужно применить подстановку k = log₂(log₂ n) или 2^k = log₂ n. Таким образом, рекуррентное соотношение как функция n будет иметь вид:

    T(n) = C₁ log₂ n + C₂(log₂(log₂ n)) log₂ n.    (3.46)

Наконец, чтобы найти константы, используем начальные условия T(2) = 1 и T(4) = 4. Для этого нужно решить следующую систему линейных уравнений:

    C₁ = 1 = T(2)
    2C₁ + 2C₂ = 4 = T(4)

Её решение: C₁ = C₂ = 1. Поэтому конечная формула для T(n):

    T(n) = log₂ n + (log₂(log₂ n)) log₂ n ∈ Θ((log(log n)) log n).    (3.47)

На следующем шаге мы рассмотрим многократные замены переменной или функции.

Предыдущий шаг Содержание Следующий шаг