Как бы я сделал рекуррентное соотношение для алгоритма, подобного этому?

Question

Мне нужно найти рекуррентное соотношение для числа умножений, выполненных для этого алгоритма, который находит основание ^ n, но я действительно не знаю, как это сделать из-за IF в нижней части.

public int reduceAndConquer(int base, int n){
 if(n == 1) return base;
 if(n == 2) return base*base;
 else{
   int total = reduceAndConquer(base, n/2);
   if(n%2 == 0) return total*total;
   return total*total*base;
 } 
}

Поскольку это либо 1, либо 2 умножения в зависимости от того, является ли оно четным или нечетным, я не уверен, как превратить это в отношение.Любой вклад будет полезен.

Answer 1

Я думаю, что вы можете делать четные / нечетные ветви в рекуррентном отношении:

T(n) = T(n/2)+1          for n even
T(n) = T(floor(n/2))+2   for n odd

или другой способ выразить то же самое:

T(2k) = T(k)+1
T(2k+1) = T(k)+2

Или, если вы действительно хотите иметь одну формулу:

T(n) = T(floor(n/2)) + 1 + n%2

где n% 2 - это, конечно, сокращение для n- (2 * floor (n / 2))