精华内容
下载资源
问答
  • 数值的整数次方

    2021-01-03 14:45:36
    数值的整数次方

    题目描述:
    实现函数double Power(double base, int exponent),求base的exponent次方。不得使用库函数,同时不需要考虑大数问题。

    链接:https://leetcode-cn.com/problems/shu-zhi-de-zheng-shu-ci-fang-lcof

    1. 常规方法

    求该数的幂次,则直接对该数挨个乘上该数有多少个即可。

    代码:

    class Solution {
    public:
        double myPow(double x, int n) {
            if(n == 0)
                return 1;
            long Power = n;
            if(Power < 0)
            {
                Power = -Power;
                x = 1 / x;
            }
            double ret = 1;
            for(long i = 0; i < Power; ++i)
                ret *= x;
            return ret;
        }
    };
    

    当n过大时,程序会超时。

    2. 快速幂

    百度释义: 快速幂就是快速算底数的n次幂。其时间复杂度为 O(log₂N), 与朴素的O(N)相比效率有了极大的提高。

    举个例子:
    在这里插入图片描述
    具体细节可看代码

    代码:

    class Solution {
    public:
        double myPow(double x, int n) {
            if(n == 0)
                return 1;
            long Power = n;
            if(Power < 0)
            {
                Power = -Power;
                x = 1 / x;
            }
            double ret = 1;
            while(Power)//快速幂
            {
                if(Power & 1)//此时为1,则乘积运算
                    ret *= x;
                x *= x;//该数继续往后走
                Power >>= 1;//幂次移位
            }
            return ret;
        }
    };
    
    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 3,337
精华内容 1,334
关键字:

数值的整数次方