快速设计一个高效的求a的n次幂的算法

题目

设计一个高效的求a的n次幂的算法

思路

• 采用for循环，比如2的三次方（3^2）,循环3次，222 = 8，时间复杂度为O(n);
• O(n)往下就是O(log(n))了，对于增长到指定数类的题目，当基数呈指数级增长时（2,4,8,16,32,64,128），时间复杂度为O(log(n)),这里就是要让a的指数从1到n呈指数增长，而不是1,2,3…n这样子
• 所以考虑让a的指数翻倍增长，即(1,2,4,8…n),即每次res=resres (res初始为a)而不是res=resa ,这样的话res=2^k, 每次res翻倍k 可能会超过n，所以需要判断条件

代码实现

/*
求a的n次幂
时间复杂度为o(n)
*/
function pow1($a, $n) {
    $res = 1;
    for ($i = 0; $i < $n; $i++) {
        $res *= $a;
    }
    return $res;
} 

/*
求a的n次幂
时间复杂度为o(log(n))
*/
function pow2($a, $n) {
    $res = $a;
    $ex = 1;//$res的指数,用于判断$res*$res后指数是否大于n 
    if ($n == 0) {
        return 1;
    }
    //$res翻倍 
    while (($ex << 1) <= $n) {//左移一位即翻倍
        $res = $res * $res;
        $ex <<= 1;
    }
    //$res不能翻倍
    //这里递归调用，将$a^(n-$ex)继续按照翻倍的方式进行增大，再乘以之前得到的$res即可得到结果 
    //n-ex即剩余的*$a的次数 ，比如5^2,经过前面2次的循环，仅剩下一次（5-4）
    $n = $n - $ex;
    //递归调用，让剩余的*a次数继续从1按照指数的形式增长
    return $res * pow2($a, $n);//16*2=32
}
echo pow2(2, 5);