再帰呼び出しの計算量

質問

再帰呼び出しを用いた関数の計算量を求める方法がわからないので質問させていただきます．
xのn乗を再帰呼び出しを用いて求める関数に関して，計算量を求める問題なのですが，どのような方針で求めればよいのでしょうか？

int exponent(int x, int n)
{
　　if(n == 0){
　　　　return 1;
　　}else{
　　　　return x * exponent(x, n-1);
　　}
}

exponentがn回呼ばれるからO(n)というのは間違いでしょうか？

回答No.1

Tacosan · ベストアンサー

計算量は n のみに依存し x には依存しません. なので, exponent(x, n) の計算量を T(n) とおきます.
T(0) = O(1), T(n) = T(n-1) + O(1)
と書けます. この漸化式を解けば T(n) = O(n).
「exponent が n回呼ばれるから O(n)」というのは省略しすぎです. exponent の中の (再帰呼び出し以外の) 計算量が O(n) だったら, そのようには言えませんよね.
「exponent の中で再帰呼び出し以外の計算量が O(1) で, exponent そのものは都合 n回呼び出されるから O(n)」とまで書いてあればいいかもしれない. 読む人によってよいとしたりだめとしたりするかもしれません.

お礼

回答ありがとうございます．

なるほど，漸化式を用いて求めればいいんですね．
詳しい説明，ご忠告ありがとうございました．