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

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

В начальном условии (при n = 1) метод выполняет основные действия, приведённые на рисунке 1.

Рис.1. Последовательность действий, выполняемых функцией из примера 1.1 при начальном условии

Перед их выполнением программа должна сохранить низкоуровневую информацию (например, параметры или адрес возврата). Считаем, что это требует а₀ единиц времени, где а₀ - просто константа. Следующее действие - проверка условия со временем выполнения а₁. Поскольку результат - True, следующее действие - это переход к третьей строке метода, который требует а₂ единиц времени. Наконец, на последнем шаге метод возвращает значение 1, требуя а₃ единиц времени. Итого при n = 1 методу нужно а = а₀ + а₁ + а₂ + а₃ единиц времени. Таким образом, можно считать, что T(1) = а. Точное значение а для асимптотической сложности вычисления метода безразлично. Важно только то, что а - постоянная величина, не зависящая от n.

Действия при выполнении рекурсивного условия (когда n > 1) приведены на рисунке 2.

Рис.2. Последовательность действий, выполняемых функцией из примера 1.1 при рекурсивном условии

Пусть

       ₅            
   b = ∑ b_i - 
      ⁱ⁼⁰

общее время хранение низкоуровневой информации, проверка условия, переход к рекурсивному условию, вычитание единицы из n, добавление n к результату рекурсивного вызова и возвращение результата, также являющееся константой, точное значение которой не важно для асимптотической сложности вычисления. Но, кроме b, необходимо оценить время на рекурсивный вызов. Поскольку он решает полную задачу размера n - 1, можно определить его как T(n - 1), а всё рекуррентное соотношение T(n) можно определить следующим образом:

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

где, например, T(3) = T(2) + b = T(1) + b + b = a + 2b.

Хотя T правильно описывает стоимость вычисления алгоритма, выяснить порядок её роста непросто из-за её рекурсивности. Поэтому следующим шагом анализа будет преобразование рекурсивной функции в эквивалентную нерекурсивную формулу. Этот процесс называют "решением" рекуррентного соотношения. В данном случае нетрудно видеть, что T(n) - линейная функция n:

    T(n) = b(n - 1) + a = b ⋅ n - b + a ∈ Θ(n)    .

В дальнейшем мы будем раасматривать общие методы решения рекуррентных соотношений.

Кроме того, в дальнейшем мы будем упрощать рекуррентные соотношения ради облегчения их анализа. Рассмотрим, например, код из примера 2.9. Связанная с ним функция стоимости выполнения может быть определена как:

       a,          если n = 1,
T(n) = T(n/2) + b, если n > 1 и n - чётное,	(3.19)
       T(n/2) + c, если n > 1 и n - нечётное.

Это рекуррентное соотношение является сложным для анализа по двум причинам. С одной стороны, оно содержит более одного рекурсивного условия. С другой - здесь не исключена работа с функцией floor(), связанной с техническими особенностями её реализации и требующей более сложной математики (например, неравенств). Более того, для определения порядка роста этой функции нет нужды усложнять её проверкой чётности n и прочими лишними деталями. Поскольку алгоритм опирается на решения подзадач (примерно - в случае нечётного n) половинного размера, вместо (3.19) можно работать со следующим рекуррентным соотношением:

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

Кроме того, в (3.20), используемой взамен (3.19), мы также предположим, что размер задачи (n) будет достаточно высокой степенью двух.

Таким образом, в дальнейшем мы будем рассматривать рекуррентные соотношения только с одним рекурсивным условием, которое не содержит функций floor() или ceiling(). Это позволит нам находить точные нерекурсивные формулы рекуррентных соотношений, чей порядок роста можно оценивать жёсткими асимптотическими границами Θ.

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

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