На этом шаге мы рассмотрим еще несколько примеров использования рекуррентных соотношений.

Тонкость рекуррентных соотношений при делении размера задачи на целочисленную константу k ≥ 2 заключается в том, что в них не должно быть начального условия для n = 0. Математически оно никогда не достижимо, и мы не сможем получить значение i на шаге 3 метода расширения. Ловушка кроется в том, что аргументом функции T(n) должно быть только целое число, поэтому дробь n/k на самом деле предполагает целочисленное деление. А это значит, что следующим за T(1) расширением будет не T(1/k), а T(0). Поэтому для правильного применения метода расширения в рекуррентные соотношения нужно включать дополнительное начальное условие, чаще всего для n = 1.

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

Рассмотрим следующее рекуррентное соотношение:

           а,                    если n = 0
    T(п) =                                     (3.24)
           T(n - 1) + b * n + c, если n > 0.

Процесс его расширения:

  T(n) = T(n - 1) + b * n + с = [T(n - 2) + b(n - 1) + c] + b * n + c = 
       = T(n - 2) + 2b * n - n + 2c = [T(n - 3) + b(n - 2) + c] + 2b * n - b + 2c = 
       = T(n - 3) + 3b * n - b(1 + 2) + 3c = [T(n - 4) + b(n - 3) + c] + 3b * n - b(1 + 2) + 3c = 
       = T(n - 4) + 4b * n - b(1 + 2 + 3) + 4c = 
       .   .   .
       = T(n - i) + i * b * n - b(1 + 2 + 3 + ... + (i - 1)) + i * c,

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

                                 _i-1
 T(n) = T(n-i) + i * b * n - b * ∑j + i * c = T(n-i) + i * b * n - b(i - 1) i/2 + i * c. (3.25)
                                 ^j=1

Два распространённых заблуждения при использовании сумм в формулах на шаге i:

(1) использование i в качестве индексной переменной суммы и
(2) выбор n в качестве её верхнего предела.

Важно отметить, что верхним пределом суммы является i - 1, откуда следует, что i не может быть индексной переменной суммы.

Наконец, начальное условие T(0) достигается при i = n, поэтому подстановка его значения в (3.25) даёт формулу

    T(n) = b * n² - b * n(n - 1)/2 + c * n + a = b * n² /2 + (c + b/2)/n + a ∈ Θ(n²),

которая является полиномом 2-й степени.

Следующее рекуррентное соотношение появляется в алгоритмах типа "разделяй и властвуй", таких, например, как сортировка слиянием:

            a,   если n = 1,    
    T(n) =                                            (3.26)
            2T(n/2) + b * n + c, если n > 1

Процесс его расширения:

    T(n) = 2T(n/2) + b * n + с = 2[2T(n/4) + b * n/2 + с] + b * n + с = 
         = 4T(n/4) + 2b * n + 2с + с = 4[2T(n/8) + b * n/4 + c] + 2b * n + 2c + c = 
         = 8T(n/8) + 3b * n + 4c + 2c + c = 8[2T(n/16) + b * n/8 + c] + 3b * n + 4c + +2c + c = 
         = 16T(n/16) + 4b o n + 8c + 4c + 2c + c = 
         .   .   .
         = 2ⁱT(n/2ⁱ) + i * b * n + c(1 + 2 + 4 + ... + 2^i-1).

И здесь в квадратных скобках - расширения членов, содержащих T. В этом случае скобки особенно полезны, поскольку каждый из расширяемых членов должен умножаться на 2. Студентам всегда стоит использовать их, так как пренебрежение ими может приводить к многочисленным ошибкам.

В данном случае общая формула содержит частичную сумму геометрической прогрессии

                                    _i-1
    T(n) = 2ⁱT(n/2ⁱ) + i * b * n + c ∑ 2^j = 2ⁱT(n/2ⁱ) + i * b * n + c(2ⁱ - 1).	(3.27)
                                    ^j=1

Начальное условие T(1) достигается при n/2ⁱ = 1, откуда следует, что i = log₂n. Поэтому подстановка i в (3.27) даёт:

    T(n) = nT(1) + b * n log₂ n + c(n - 1) = b * n log₂ n + n(a + c) - c ∈ Θ(n log n),

где старший член - b * n log₂ n.

На следующем шаге мы рассмотрим основную теорему.

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