找回密码
 立即注册
  • QQ空间
  • 回复
  • 收藏

Pow的实现

C++关于pow()函数的实现:
解法1
采用递归的形式,时间复杂度为log(N),
递归终止条件,当n == 0时,返回1;
如果n < 0,返回1 / myPow(x, -n);
如果n为奇数,将n - 1传入myPow继续计算;
如果n为偶数,传入x * x, n / 2,效果等同于x , n
double myPow(double x, int n)
{
    if(n == 0)
        return 1.0;
    if(n < 0)
        return 1.0 / myPow(x, -n);
    if(n % 2)
        return x * myPow(x, n - 1);
    return myPow(x * x, n / 2);
}
解法2
采用循环的形式,时间复杂度为log(N),空间复杂度小于递归形式
当n > 0时执行循环,如果n是奇数,就让res *= x
如果n是偶数,x *= x; n >>=1;(n >>=1; 等价于n = n / 2;)
double myPow(double x, int n)
{
    double res = 1.0;
    if(n < 0){
        x = 1.0 / x;
        n = -n;
    }
    while(n){
        if(n & 1)
            res *= x;
        x *= x;
        n >>= 1;
    }
    return res;
}
回复

使用道具 举报

说点什么

您需要登录后才可以回帖 登录 | 立即注册
HOT • 推荐

© 2018 今日头条

中国互联网举报中心 京ICP证140140号

粤-非经营性-2017-0062

互联网药品信息服务资格证书

跟帖评论自律管理承诺书 违法和不良信息举报:010-58362200 公司名称:Quater情感在线 客服QQ:2243108352(站长自定义)