剑指offer——面试题11：数值的整数次方

Solution1：基本算法

累乘，时间复杂度为O(n)

要考虑全部情况：指数 < 0, == 0 和 > 0.

注意在 if…else if的语句中最后一个最好写成else，否则在牛客网上编译报错

class Solution {public:    double Power(double base, int exponent) {        double res=1.0;        if(exponent>0){            while(exponent-->0)                res*=base;            return res;        }        else if(exponent == 0){            return res;        }        else {            int abs_exp=-exponent;            while(abs_exp-->0)                res*=base;            return (1.0/res);        }    }};

Solution2：

优化版的算法：时间复杂度

O(logn) O ( l o g n ) $O(log n)$

当n为偶数：

an=an/2∗an/2 a n = a n / 2 ∗ a n / 2 $a^n =a^{n/2}*a^{n/2}$

当n为奇数：

an=a(n−1)/2∗a(n−1)/2∗a a n = a ( n − 1 ) / 2 ∗ a ( n − 1 ) / 2 ∗ a $a^n = a^{(n-1)/2} * a^{(n-1)/2} * a$

书上的代码有坑，肾重啊肾重！

class Solution {public:    double Power(double base, int exponent) {        int abs_exp = abs(exponent);        if (abs_exp == 0)            return 1;        else if (abs_exp == 1)            return base;        double res = Power(base, abs_exp/2);        res *= res;        if (abs_exp & 1)            res *= base;        if (exponent < 0)            res = 1/res;        return res;    }};

转载地址：http://ethdb.baihongyu.com/

你可能感兴趣的文章

【Redis最佳实践】使用DCS Redis实现分布式锁