Рубрики

Анализ алгоритма | Набор 4 (решение повторений)

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

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

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

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
    <= cn/2Log(n/2) + n
    =  cnLogn - cnLog2 + n
    =  cnLogn - cn + n
    <= cnLogn

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

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

           cn2
         /      \
     T(n/4)     T(n/2)

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

                cn2
           /           \      
       c(n2)/16      c(n2)/4
      /      \          /     \
  T(n/16)     T(n/8)  T(n/8)    T(n/4) 
Breaking down further gives us following
                 cn2
            /            \      
       c(n2)/16          c(n2)/4
       /      \            /      \
c(n2)/256   c(n2)/64  c(n2)/64    c(n2)/16
 /    \      /    \    /    \       /    \  

To know the value of T(n), we need to calculate 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 geometrical progression with ratio 5/16.

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

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

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

Есть три следующих случая:
1. Если f (n) = Θ (n c ), где c <Log b a, то T (n) = Θ (n Log b a )

2. Если f (n) = Θ (n c ), где c = Log b a, то T (n) = Θ (n c Log n)

3. Если f (n) = Θ (n c ), где c> Log b a, то T (n) = Θ (f (n))

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

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

Примеры некоторых стандартных алгоритмов, сложность времени которых можно оценить с помощью метода Master
Сортировка слиянием : T (n) = 2T (n / 2) + Θ (n). Это относится к случаю 2, так как c равно 1 и Log b a] также равно 1. Таким образом, решение is (n Logn)

Двоичный поиск : T (n) = T (n / 2) + Θ (1). Это также относится к случаю 2, так как c равно 0 и Log b a также равно 0. Таким образом, решение равно Θ (Logn)

Примечания:
1) Нет необходимости, чтобы повторение вида T (n) = aT (n / b) + f (n) можно было решить с помощью основной теоремы. Приведенные три случая имеют некоторые пробелы между ними. Например, рекуррентность T (n) = 2T (n / 2) + n / Logn не может быть решена с использованием основного метода.

2) Случай 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)

Практические проблемы и решения по основной теореме.

Далее — Анализ алгоритма | Набор 5 (Амортизированный анализ Введение)

Ссылки:
http://en.wikipedia.org/wiki/Master_theorem
MIT видео лекция по асимптотической записи | Рецидивы | Замена, Мастер Метод
Введение в алгоритмы 3-е издание Клиффорд Стейн, Томас Х. Кормен, Чарльз Э. Лейзерсон, Рональд Л. Ривест

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

Рекомендуемые посты:

Анализ алгоритма | Набор 4 (решение повторений)

0.00 (0%) 0 votes