Как сделать рекуррентные соотношения?

Итак, день назад нас учили рекуррентным отношениям, и нам дали несколько кодов для практики:

int pow(int base, int n){

if (n == 0)

  return 1;

else if (n == 1)

  return base;

else if(n%2 == 0)

  return pow(base*base, n/2);

else

 return base * pow(base*base, n/2);

}

Самое дальнее, что я получил, чтобы получить его закрытую форму, это T (n) = T (n/2 ^ k) + 7k. Я не уверен, как пойти дальше, поскольку примеры, данные нам, были простыми и не очень помогают. Как вы на самом деле решаете рекуррентное отношение этого кода?


recurrence algorithm time-complexity
person user3249400    schedule 29.01.2014    source источник
comment
откуда взялась цифра 7? что такое к? Должна ли T обозначать сложность алгоритма?   -  person amit    schedule 29.01.2014
comment
7 - это то, что я получил, получив количество операций кода, и, кстати, k = log n И да, T обозначает сложность алгоритма.   -  person user3249400    schedule 29.01.2014

Ответы (1)


arrow_upward
1
arrow_downward

Давайте посчитаем только умножения в вызове pow, обозначенного как M(N), предполагая, что они преобладают в стоимости (в настоящее время совершенно неверное предположение).

Изучив код, мы видим, что:

M(0) = 0 (без умножения для N=0)

M(1) = 0 (без умножения для N=1)

M(N), N>1, N четное = M(N/2) + 1 (для четного N рекурсивный вызов после одного умножения)

M(N), N>1, N нечетное = M(N/2) + 2 (для нечетного N рекурсивный вызов после одного умножения, за которым следует второе умножение).

Это повторение немного усложняется тем, что оно по-разному обрабатывает четные и нечетные целые числа. Мы обойдем это, рассматривая последовательности только четных или нечетных чисел.

Давайте сначала рассмотрим случай, когда N является степенью числа 2. Если мы повторим формулу, мы получим M(N) = M(N/2) + 1 = M(N/4) + 2 = M(N/8) + 3 = M(N/16) + 4. Мы легко обнаруживаем шаблон M(N) = M(N/2^k) + k, так что следует решение M(2^n) = n. Мы можем записать это как M(N) = Lg(N) (логарифм по основанию 2).

Точно так же N = 2^n-1 всегда будет давать нечетные числа после деления на 2. У нас есть M(2^n-1) = M(2^(n-1)-1) + 2 = M(2^(n-2)-1) + 4... = 2(n-1). Или M(N) = 2 Lg(N+1) - 2.

Точное решение для общего N может быть довольно сложным, но мы видим, что Lg(N) <= M(N) <= 2 Lg(N+1) - 2. Таким образом, M(N) равно O(Log(N)).

person Yves Daoust    schedule 29.01.2014