快速幂

李坤泽 · 2019-11-02 17:13:38 · 个人记录

x^y如何简化? 1.

int pow(int x,int y){
    int ans;
   for(int i=1;i<=y;i++) ans*=x;
   return ans;
}

这时计算要进行Y次，即O等于Y；\ 但是，x^y=x^(1+1+....+1)\ 所以可以用二分来处理这Y个一\ 也举i是把Y转化为二进制，通过位运算来判断

int pw(int x,int y){
    int ans=1; tem=x;
   while(p){
     if(p & 1){
        ans*=tem;
    }
    tem*=tem;
    p>>=1;
   }
  return ans;
}

这是时间复杂度为O(log y)的快速幂.