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

Рекуррентное соотношение для времени выполнения кодов из примеров 1.2 и 2.4 могло бы быть таким:

            1,           если n = 1
    T(n) =                                    (3.30)
            2T(n/2) + 1, если n > 1,

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

Рекуррентное соотношение можно решить методом расширения следующим образом:

    T(n) = 2 T(n/2) + 1 = 2 [2T(n/4) + 1] + 1 = 
           = 4 T(n/4) + 2 + 1 = 4 [2T(n/8) + 1] + 2 + 1 = 
           = 8 T(n/8) + 4 + 2 + 1 = 8[2T(n/16) + 1] + 4 + 2 + 1 = 
           = 16 T(n/16) + 8 + 4 + 2 + 1 = 
           .   .   .   .
                         _i-1
           = 2ⁱT(n/2ⁱ) + ∑ 2^j = 2ⁱT(n/2ⁱ) + 2ⁱ - 1.
                        ^j=0

Начальное условие T(1) = 1 выполняется при n = 2ⁱ. Подстановка даёт:

    T(n) = n + n - 1 = 2n - 1 ∈ Θ(n)           ,

где T(n) - линейная функция n. Естественно, этот результат соответствует основной теореме (см. (3.28)), так как рекуррентное соотношение - особый случай (3.29), где a = 2, b = 2 и k = 0. Поэтому

    T(n) ∈ Θ(2^{log₂ n}) = Θ(n)              .

Рассмотрим функцию из примера 1.5. Первые два метода уменьшают размер задачи на 1. Таким образом, соответствующее им рекуррентное соотношение могло бы быть таким:

            1,          если n = 1
    T(n) =                                    
            T(n - 1) + 1, если n > 1,

что является особым случаем (3.21), где T(n) ∈ Θ(n). Третий метод делит размер исходной задачи пополам, и решения подзадач не нуждаются в последующей обработке. Поэтому его рекуррентное соотношение совпадает с (3.30).

В заключение мы рассмотрим временную сложность вычислений кодов из примеров 2.2 и 2.3. Рекуррентное соотношение для них (пренебрегая постоянными множителями):

            1,           если n < 10
    T(n) =                                    (3.31)
            T(n/10) + 1, если n ≥ 10    .

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

            1,           если n = 1
    T(n) =                                    (3.32)
            T(n/10) + 1, если n > 1    .

Обе функции равнозначны при n = 10^p и p ≥ 0.

Второе рекуррентное соотношение - особый случай (3.29), когда a = 1, b = 10 и k = 0. Таким образом, согласно основной теореме, его сложность - логарифмическая, поскольку T(n) ∈ Θ(n^k log n) = Θ(log n).

Тот же результат можно получить методом расширения:

    T(n) = T(n/10) + 1 = T(n/100) + 1 + 1 = 
         = T(n/10²) + 2 = T(n/1000) + 1 + 2 = 
         = T(n/10³) + 3 = T(n/10000) + 1 + 3 = 
         = T(n/104) + 4 =
         .   .   .   .
         = T(n/10ⁱ) + i.

Начальное условие выполняется при n/10ⁱ = 1, то есть при i = log₁₀ n.

Подстановка даёт:

    T(n) = T(1) + log₁₀ n = 1 + log₁₀ n ∈ Θ(log n)                   .

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

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