Написание рекуррентного отношения для метода

Question

У меня есть немного кода и мне нужно написать рекуррентное отношение для него. Код просто вычисляет 2, возведенные в n-ую степень. Любая помощь приветствуется.

public static int two(int n) {

     if (n==0) {
       return 1;
     } else if (n%2 == 0) {
       int x = two(n/2);
       return x*x;
     } else { 
       return 2 * two(n-1)
}

Answer 1

Формулировка функции почти является рекуррентным соотношением. По сути, все, что вам нужно сделать, это выполнить изменение переменных, чтобы аргумент two в рекурсии был n. Например, возьмите следующую функцию Фибоначчи:

public static int fib(n) {
    if (n==0) {
        return 1;
    } else if (n==1) {
        return 1;
    } else {
        return fib(n-1) + fib(n-2);
    }
}

Вы не захотите использовать эту реализацию, поскольку она ужасно неэффективна, но облегчает написание отношения повторения:

fib<sub>0</sub>=1
fib<sub>1</sub>=1
fib<sub>n+2</sub> = fib<sub>n+1</sub> + fib<sub>n</sub>

С примером Фибоначчи вам на самом деле не нужно выполнять изменение переменных. Однако с вашей функцией two это упростит запись отношения.

Answer 2

Строки, которые не имеют рекурсивных вызовов, выполняются в постоянное время, которое мы будем называть c.

T(n)=T(n-1)+c if n is odd.
T(n)=T(n/2)+c if n is even.

После каждого рекурсивного вызова с n нечетным следующим рекурсивным вызовом мы будем с n-1 дажеТаким образом, в худшем случае мы начинаем с нечетного n -> четное n-1 -> (n-1) / 2 нечетное -> (n-1) / 2-1 четное и так далее ...

Если, например, мы начинаем с n = 19, то 19 нечетное -> 18 четное -> 9 нечетное -> 8 четное -> 4 четное -> 2 четное -> 0.

Глубина рекурсивного дерева составляет около lgn, и, поскольку на каждом уровне есть c операций, время выполнения равно clgn = O (lgn).