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

Question

假设您要计算ⁿ。一个简单的算法将 a、n 乘以如下：

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)

很困惑，那么 n=2 ^k是怎么回事，为什么 k 只显示在第二个例子中？不明白这如何转化为 O(logn) 时间复杂度......

Answer 1

第二种算法在一般情况下不起作用；它仅在存在一些 k 以便您可以编写 n = 2 ^k时才有效。如果有 ak 可以做到这一点，那么通过取等式两边的对数，你会得到 log ₂ n = k。所以：

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

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

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

这更清楚地在 O(log n) 时间内运行，因为循环运行 log ₂ n 次并且 O(1) 在每次迭代中工作。

我认为“不失一般性”说 n 是 2 的完美幂是不公平的，因为并非所有数字都是！上面的代码只有在 n 是 2 的幂时才有效。您可以通过使用重复平方算法将其推广到非二次方，该算法具有 O(log n) 复杂度，但适用于任何幂。

希望这可以帮助！