java - (c^k) の Big O 表記

Question

次のコードは、O(n) を返します。時間計算量が O(c^k) の for ループをコーディングするにはどうすればよいですか?

int power(int x, unsigned int y)
{
    if( y == 0)
        return 1;
    else if (y%2 == 0)
        return power(x, y/2)*power(x, y/2);
    else
        return x*power(x, y/2)*power(x, y/2);

}

Answer 1

何を求めているのかわかりませんが、再帰の繰り返しを取り除くだけで、このコードを明確に変更して多くのことを勝ち取ることができます (同じことを 2 回再帰的に計算しないでください)。

if (y%2 == 0) {
    int res = power(x, y/2);    
    return res * res;
}

このように書くと、再帰の代わりに while ループを書くことができます。