Установка и решение рекуррентного отношения для рекурсивной функции? - PullRequest
Новая
       43

Установка и решение рекуррентного отношения для рекурсивной функции?

3 голосов
/ 14 февраля 2012

Я нахожусь в процессе изучения повторения Java, но застрял в следующем вопросе. 

void f(int n) {
    if (n<=1) return;
    f(n/2);
    System.out.writeln("still continuing...");
    f(n/2);
    f(n/2);
}

У меня есть два вопроса по этому поводу.

  1. если мы говорим, что T (n) - это количество строк, которые печатает программа, а n - это ввод, какова будет формула повторения для T (n)?

  2. Как мне решить рекурсию из вопроса 1 без использования основной теоремы?

ура

Ответы [ 2 ]

3 голосов
/ 14 февраля 2012

Начнем с формулы для значения T (n).Мы знаем следующее:

  1. Вызов f с 0 или 1 в качестве аргумента занимает время O (1)
  2. Вызов f с большим значением делает три вызова f (n / 2)и выполняет постоянное количество другой работы.

Следовательно, мы можем получить следующее повторение:

  • T (1) ≤ 1
  • T(n) ≤ 3T (n / 2) + 1

Обратите внимание, что здесь я использую термин «+ 1» вместо термина «+ O (1)».Это математически неверно, но так как мы ищем окончательный результат, выраженный в нотации big-O, в любом случае, это не будет большой проблемой.

Теперь, как мы будем пытаться решить эту проблему??Один из вариантов - подключить произвольное значение для n и посмотреть, что произойдет.Начнем с (при условии, что n> 1), что

T (n) ≤ 3T (n / 2) + 1

Теперь давайте подумаем об этих вызовах T(н / 2).Если n / 2> 1, то получаем, что

T (n) ≤ 3T (n / 2) + 1

≤ 3 (3T (n / 4) + 1) + 1

= 9T (n / 4) + 3 + 1

Теперь давайте расширим это усиление:

T (n) ≤ 9T (n / 4) + 3 + 1

≤ 9 (3T (n / 8) + 3) + 3 + 1

= 27T (n / 8) + 9 +3 + 1

В этот момент мы видим появление паттерна.После итераций рекурсии мы получаем, что общая выполненная работа составляет

T (n) = 3 i T (n / 2 i )+ sum (i = 0 to i - 1) 3 i

Этот процесс завершается, когда n / 2 i ≤ 1, что происходит, когда i ≈LG N.Если мы подключим lg n, мы получим

T (n) ≤ 3 lg n T (1) + сумма (i = от 0 до i - 1) 3 i )

≤ 3 lg n + сумма (i = 0 до i - 1) 3 lg n

Теперь 3 lg n = 3 (log3 n / log3 2) = 3 log3 n 1 / log3 2 = n 1 / log3 2 , так что все это составляет

T (n) ≤ n 1 / log3 2 + сумма (i = 0 до (lg n)) - 1) 3 i

Используя формулу для сумм геометрических рядов, этот последний член равен (3 lg n - 1) / 2,который в итоге расширяется до O (n 1 / log3 2 ), поэтому в целом это выражение равно O (n 1 / log 3 2 ).

Но эта формула действительно безобразна.Можем ли мы упростить это?Ну, у нас есть это:

1 / log 3 2 = log 2 3

Что дает нам этовремя выполнения равно O (n lg 3 ), что примерно равно O (n 1.58 ).

Надеюсь, это поможет!

0 голосов
/ 14 февраля 2012 
T(n) = 3* T(n/2)+ O(1)

Как показывает теорема, ответ должен быть O (n ^ (lg 3)).

Для получения более подробной информации вы можете обратиться к разделу «Введение в алгоритм» Кормена и др., См. Главу 4. Решение рекуррентных уравнений довольно сложно. Но обычно метод сначала догадывается, а затем доказывает использование подстановки.

...