algorithm - アルゴリズム分析

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

ステップごとに 1 つの乗算のみを実行しています。したがって、関係は次のようになります。

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