为什么这个算法叫快速幂运算呢

Question

为什么这个算法叫快速幂运算呢？？这不和普通的一样吗?

long pow_2(int b)
{
    long x=2;
    long res=1;
    while(b>0)
    {
        if(b&1)
        {res=res*x;}
        b>>=1;
        x=x*x;
    }
    return res;
}

Answer 1

该回答引用ChatGPT

快速幂算法（也称为二分幂算法或平方-乘算法）是一种用于计算幂运算的快速算法，它利用了幂运算具有重叠子问题和最优子结构的特性，可以在 $O(\log n)$ 的时间复杂度内计算 $x^n$ 的值。

相比于普通的幂运算算法，快速幂算法的主要优势在于它的时间复杂度更低，尤其是当指数 $n$ 很大时，能够显著提高计算效率。这是因为快速幂算法使用了一种将指数 $n$ 按照二进制拆分成若干个小的幂的方法，使得每次计算时只需要考虑指数的一半大小，从而可以大大减少乘法的次数。

在给出的 C++ 代码中，我们实现了一个计算 $2^b$ 的快速幂算法，其具体实现方式是将指数 $b$ 按照二进制拆分成若干个小的幂，每次只考虑最低位的幂是否为 $1$，并累积结果 $res$ 和底数 $x=2$ 的幂，同时每次将底数 $x$ 的幂平方以加速计算。最终，当指数 $b$ 的所有二进制位都被处理完后，算法返回结果 $res$。

因此，这个算法被称为快速幂算法，因为它比普通的幂运算算法更快速。