algorithm - 算法：k和n之间的关系是什么？

Question

计算 a^n 的值：

方法1：

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

如果使用方法2改进：

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

如何推断 k 和 n 之间的关系？为什么？谢谢！

Answer 1

我猜你正试图通过平方来求幂。

显然，对于 2 的幂，k = log_2 n。

Answer 2

在第一种情况下结果 = a^n，在第二种情况下结果 = a^(2^k)，所以 2^k = n 和 k = logn。当然，这仅对 2 的幂的 n 是正确的。

Answer 3

我认为在第一种情况下 a, a^2 , a^3..a^n 在第二种情况下是 a^2,a^4,A^8......A^(2^k)