这个用于计算^ 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)复杂度但适用于任何功率.

希望这可以帮助!