Chapter2: 时间复杂度分析、递归、查找与排序

13. 实战：快速设计一个高效的求a的n次幂的算法

问题

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

算法

设计思路

经验丰富的话可能一下子就想出了，但是刚开始都是设计出一般的算法，然后再考虑优化的

比如说求a的n次幂，很容易就想到了用for循环，时间复杂度为O(n)，

既然要设计一个更高效的方法，O(n)往下就是O(log(n))了，或者常数，常数就是一下子就算出来了，不太可能，所以考虑设计一个时间复杂度为O(log(n))的算法

对于增长到指定数类的题目，当基数呈指数级增长时，时间复杂度为O(log(n)),这里就是要让a的指数从1到n呈指数增长，而不是1,2,3...n这样子

所以考虑让a的指数翻倍增长，即(1,2,4,,8...n),即每次res=res*res (res初始为a) 而不是res=res*a ,这样的话res=2^k, 每次res 翻倍 k 可能会超过 n ，所以需要判断条件

代码

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

/*
求a的n次幂
时间复杂度为o(log(n))*/
int pow2(int a,int n){
    int res=a;
    int ex=1;//res的指数,用于判断res*res后指数是否大于n 
    
    if(n==0){
        return 1;
    } 
    
    //res能翻倍 
    while((ex<<1)<=n){//ex<<1即ex翻倍，效果等价于res*res 
        res=res*res;//
        ex<<=1;
    }
    //res不能翻倍
    //这里递归调用，将a^(n-ex)继续按照翻倍的方式进行增大，再乘以之前得到的res即可得到结果 
    n=n-ex;//n-ex即剩余的*a的次数 
    return res*pow2(a,n);//递归调用，让剩余的*a次数继续从1按照指数的形式增长
}