algorithm - アルゴリズム : k と n の関係は?

Question

a^n の値を計算するには:

方法 1:

  result = 1;
  for(int i = 1; i <=n; i++)
      result *= a;

method2 を使用して改善した場合:

result = a;
for(int i = 1; i <=k; i++)
    result = result * result;

k と n の関係をどのように推測できますか? なぜ？ありがとう！

Answer 1

2乗してべき乗をしようとしていると思います。

明らかに、2 のべき乗の場合、k = log_2 n です。

Answer 2

最初のケースでは a, a^2 , a^3..a^n 2番目のケースでは a^2,a^4,A^8......A^(2^k) だと思います

Answer 3

最初のケースでは結果 = a^n、2 番目のケースでは結果 = a^(2^k) であるため、2^k = n および k = logn です。もちろん、これは 2 の累乗である n に対してのみ正しいです。