请选择 进入手机版 | 继续访问电脑版

巨推链

PoWPoW
关注: 0贴子:673 排名: 2 
0 回复贴,187 次查看
<返回列表

Pow的实现

发表于 2019-5-22 12:35:03
C++关于pow()函数的实现:
解法1
采用递归的形式,时间复杂度为log(N),
递归终止条件,当n == 0时,返回1;
如果n &lt; 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 &lt; 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 &gt; 0时执行循环,如果n是奇数,就让res *= x
如果n是偶数,x *= x; n &gt;&gt;=1;(n &gt;&gt;=1; 等价于n = n / 2;)
double myPow(double x, int n)
{
    double res = 1.0;
    if(n &lt; 0){
        x = 1.0 / x;
        n = -n;
    }
    while(n){
        if(n &amp; 1)
            res *= x;
        x *= x;
        n &gt;&gt;= 1;
    }
    return res;
}
回复

使用道具 举报

  • 发布信息免费
  • 发贴彩色标题
  • 签到额外经验值

如何快速提升等级,查看[积分规则]

活动中心

查看更多>>
最新热版
会员排行
©2001-2018 巨推链 https://jutuilian.com/中国互联网举报中心 京ICP备14033863号-26 非经营性网站Powered byDiscuz!X3.3公安网备 
我们手机版广告合作客服QQ:1831288186Comsenz Inc.