алгоритм анализа

Question

У меня есть алгоритм, с помощью следующего псевдокода:

R(n) 
if(n = 1) 
    return 1 
else 
    return(R(n-1) + 2 * n + 1) 

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

Есть следующие права?

R(1) = 0 
R(n) = R(n-1) + n^2 

Answer 1

Вы выполняете только одно умножение за шаг. Таким образом, отношение будет:

R(n) = R(n-1) + 1 

Answer 2

В алгоритме, как показано R (п) рассчитывается путем сложения R (п-1) 2 * N + 1. Если 2 * n вычисляется с использованием умножения, то будет одно умножение на уровень рекурсии, таким образом, n-1 умножений при вычислении R (n).

Чтобы вычислить, что через повторение пусть M (n) - количество умножений, используемых для вычисления R (n). Граничным условием рекуррентности является M (1) = 0, а рекуррентное соотношение M (i) = M (i-1) + 1 для i> 1.

Ошибки в письменной форме «R (1) = 0; R (n) = R (n-1) + n^2 ", поскольку повторяемость для числа умножений включает в себя:
• R() уже используется как функция, которая вычисляется, следовательно, повторно используется R() как число умножений неверно
• Каждый уровень рекурсии в алгоритме добавляет одно умножение, а не n² умножения.

Примечание: R (n) = 1 + 5 + 7 + ... + 2n + 1 = 1 + 3 + 5 + 7 + ... + 2n + 1 - 3 = n²-3; то есть функция R (n) возвращает значение n²-3.