这个计算 a^n 的算法是如何重写以在 O(log n) 时间内运行的？

Suppose you want to compute aⁿ. A simple algorithm would multiply a, n times, as follows:

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

该算法需要 O(n) 时间。不失一般性，假设 n=2^k

您可以使用以下方案改进算法：

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

该算法需要 O(log n) 时间。对于任意n，可以修改算法并证明复杂度仍然是O(logn)

So confused, so how is n=2^k, and why is k only shown in the second example? Don't understand how this transformed into a O(logn) time complexity...

The second algorithm doesn't work in the general case; it only works if there is some k such that you can write n = 2^k. If there is a k where you can do this, then by taking the logs of both sides of the equality you get that log₂ n = k. Therefore:

• 该循环最多计数 k，运行 O(log n) 次。
• 因此，循环的运行时间为 O(log n)。

如果你想摆脱神秘的 k，你可以写

int result = a;
for (int i = 0; i < log2(n); i++) {
    result = result * result;
}

This more clearly runs in O(log n) time, since the loop runs log₂ n times and does O(1) work on each iteration.

我认为“不失一般性”说 n 是 2 的完美幂是不公平的，因为并非所有数字都是！上面的代码仅在 n 是 2 的幂时才有效。您可以使用以下方法将其推广到非二的幂重复平方算法 http://en.wikipedia.org/wiki/Exponentiation_by_squaring，其复杂度为 O(log n) 但适用于任何幂。

希望这可以帮助！