11. 数值的整数次方 --剑指Offer(Java版)

「爱情、让人受尽委屈。」 2022-03-10 09:20 113阅读 0赞

[github地址][github]

> 给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。

主要是考虑情况，幂 == 0, k>0, k<0.

最暴力的办法：

private double myPower(double base, int exponent) {
            if (base == 0) {
                return 0;
            }
            if (exponent == 0) {
                return 1;
            } else if (exponent < 0) {
                double res = base;
                while (exponent++ != -1) {
                    res *= base;
                }
                return 1 / res;
            } else {
                double res = base;
                while (exponent-- != 1) {
                    res *= base;
                }
                return res;
            }
        }

这个时间复杂度是O(n).并不被推荐。

我们来推导一下公式即可。

> a^n = \{1. a^(n/2) \* a^(n/2)    // 幂 n 是偶数
> 
> a^((n-1)/2) \* a^((n-1)/2) \* a   // 幂n是奇数，那么

这样就实现了O(log n)的时间复杂度

// 作者推荐算法O（log(n)）
    
        /**
         * 进行一个推导
         * <p>
         * { a^(n/2) * a^(n/2)        // 当 n 为偶数时}
         * a^n = {                                         }
         * { a^(n/2) * a^(n/2)*n        // 当 n 为奇数时}
         * 这样时间复杂度就从O（n）降为O(log(n))
         */
        public double Power(double base, int exponent) {
            // 负数情况下,先求绝对值
            int n = Math.abs(exponent);
            if (n == 0) {
                return 1;
            } else if (n == 1) {
                return base;
            }
            //a^n = {1. a^(n/2) * a^(n/2) .             (n为偶数)
            //      {2. a^((n-1)/2) * a^((n-1)/2) * a    (n为奇数)
            // n不断除2，直到n/2 == 1 or 0
            double result = Power(base, n >> 1);
    
            // 求自身平方
            result = result * result;
            // 如果 幂是奇数，那么多乘一个base
            if ((n & 1) == 1) {
                result = result * base;
            }
            // 负数情况，求其倒数
            if (exponent < 0) {
                result = 1 / result;
            }
            return result;
        }

[github]: https://github.com/RudBob/offer66