Как анализировать сложность рекуррентного отношения

В предыдущем посте мы обсуждали анализ циклов. Многие алгоритмы рекурсивны. Когда мы анализируем их, мы получаем рекуррентное соотношение для временной сложности. Мы получаем время работы на входе размера n как функцию от n и время работы на входах меньшего размера. Например, в сортировке слиянием, чтобы отсортировать заданный массив, мы делим его на две половины и рекурсивно повторяем процесс для двух половин. Наконец, мы объединяем результаты. Временная сложность сортировки слиянием может быть записана как T(n) = 2T(n/2) + cn. Есть много других алгоритмов, таких как бинарный поиск, Ханойская башня и т. д.

Есть в основном три способа решения рецидивов:

Метод замены:

Мы делаем предположение для решения, а затем используем математическую индукцию, чтобы доказать, что предположение правильное или неправильное.

For example consider the recurrence T(n) = 2T(n/2) + n

We guess the solution as T(n) = O(nLogn). Now we use induction to prove our guess.

We need to prove that T(n) <= cnLogn. We can assume that it is true for values smaller than n.

T(n) = 2T(n/2) + n
     <= 2cn/2Log(n/2) + n
       =  cnLogn – cnLog2 + n
       =  cnLogn – cn + n
    <= cnLogn

Метод рекуррентного дерева:

В этом методе мы рисуем рекуррентное дерево и вычисляем время, затрачиваемое на каждый уровень дерева. Наконец, мы суммируем работу, проделанную на всех уровнях. Чтобы нарисовать дерево повторения, мы начинаем с заданного повторения и продолжаем рисовать, пока не найдем закономерность среди уровней. Узор обычно представляет собой арифметический или геометрический ряд.

For example, consider the recurrence relation 

T(n) = T(n/4) + T(n/2) + cn²

            cn²
            /      
  T(n/4)     T(n/2)

If we further break down the expression T(n/4) and T(n/2), 
we get the following recursion tree.

                    cn²
              /                  
    c(n²)/16          c(n²)/4
   /                    /        
T(n/16)  T(n/8)  T(n/8)    T(n/4) 

Breaking down further gives us following

                       cn² 
                /                     
       c(n²)/16              c(n²)/4
    /                           /          
c(n²)/256  c(n²)/64  c(n²)/64   c(n²)/16
 /                /          /            /      

To know the value of T(n), we need to calculate the sum of tree 
nodes level by level. If we sum the above tree level by level, 

we get the following series T(n)  = c(n^2 + 5(n^2)/16 + 25(n^2)/256) + ….
The above series is a geometrical progression with a ratio of 5/16.

To get an upper bound, we can sum the infinite series. We get the sum as (n²)/(1 – 5/16) which is O(n²)

Мастер-метод:

Мастер-метод — это прямой путь к решению. Мастер-метод работает только для повторений следующего типа или для повторений, которые могут быть преобразованы в следующий тип.

T(n) = aT(n/b) + f(n) where a >= 1 and b > 1

Имеются следующие три случая:

• Если f(n) = O(n ^c ), где c < Log _b a , то T (n) = Θ (n ^{Log _b a} )
• Если f(n) = Θ(n ^c ), где c = Log _b a, то T(n) = Θ(n ^c Log n)
• Если f(n) = Ω(n ^c ), где c > Log _b a, то T(n) = Θ(f(n))

Как это работает?

Основной метод в основном основан на методе рекуррентного дерева. Если мы нарисуем рекуррентное дерево T(n) = aT(n/b) + f(n), мы увидим, что работа, проделанная в корне, равна f(n), а работа, проделанная на всех листьях, равна Θ(n ^c ), где c — Log _b a. И высота рекуррентного дерева Log _b n

В методе рекуррентного дерева мы вычисляем общую проделанную работу. Если работа, проделанная на листьях, полиномиально больше, то листья являются преобладающей частью, и наш результат становится работой, проделанной на листьях (случай 1). Если работа, проделанная на листьях и корне, асимптотически одинакова, то наш результат равен высоте, умноженной на работу, проделанную на любом уровне (случай 2). Если работа, выполненная в корне, асимптотически больше, то нашим результатом будет работа, выполненная в корне (случай 3).

Примеры некоторых стандартных алгоритмов, временная сложность которых может быть оценена с помощью мастер-метода.

• Сортировка слиянием: T(n) = 2T(n/2) + Θ(n). Оно падает в случае 2, так как c равно 1 и Log _b a] также равно 1. Таким образом, решение равно Θ(n Logn)
• Бинарный поиск: T(n) = T(n/2) + Θ(1). Это также падает в случае 2, поскольку c равно 0, а Log _b a также равно 0. Таким образом, решение Θ (Logn)

Заметки:

• Нет необходимости, чтобы повторение формы T (n) = aT (n / b) + f (n) можно было решить с помощью основной теоремы. Приведенные три случая имеют некоторые пробелы между собой. Например, повторяемость T(n) = 2T(n/2) + n/Logn не может быть решена с помощью эталонного метода.
• Случай 2 может быть расширен для f(n) = Θ(n ^c Log ^k n)
  Если f(n) = Θ(n ^c Log ^k n) для некоторой константы k >= 0 и c = Log _b a, то T(n) = Θ(n ^c Log ^k+1 n)

Подробнее см.: Проектирование и анализ алгоритмов.

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