16.数值的整数次方
一、 题目
实现 pow(x, n) ,即计算 x 的 n 次幂函数(即,xn)。不得使用库函数,同时不需要考虑大数问题。
示例 1:
示例 2:
示例 3:
提示:
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/shu-zhi-de-zheng-shu-ci-fang-lcof
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
二、 快速幂
幂运算是我们最常用的运算之一。如果我们要求 x 的 N 次幂,那么想当然的就会写出一个 N 次的循环,然后累乘得到结果。这种幂运算的复杂度是O(N)。
那么有没有更快的运算方式呢?
在计算机领域有一种常用的快速幂算法:蒙哥马利幂(Montgomery reduction)算法
。将复杂度从O(N) 降到了 O(logN)
2.1 思路一:递归
若 N 为偶数,可以先求 xN/2,然后再平方。
若 N 为奇数,可以先求 x(N-1)/2,然后再平方,再乘以x
快速幂的最基础思想就是上面两条了。
求解 xN/2,x(N-1)/2 时也可以用到上面的思路,每次将指数除以2,每次都可以将复杂度降低一半,知道最后指数为1。
Swift实现
这里不考虑大数,仅作为思路展示
2.2 思路二:二进制拆分
我们以 x14 为例进行推导。
x14(10) = x1110(2) = x1000(2) * x100(2) * x10(2)
换个方向,更直观:
x1110(2) = x10(2) * x100(2) * x1000(2)
推论:
设 x 的 N 次幂等于 res
1: 在指数 N 的二进制形式下,从最低位开始左移一位,x自乘一次(和指数N左移一位保持一致)
如果当前位为1
当前位a到最低位,中间位全部置0时表示的值b,xb的累乘
如果当前位位0
执行1
循环直到指数N等于0
当前位
指数b
res
1110
0
x0(2)
111
0
10
x10(2)
11
10
100
x10(2) * x100(2)
1
110
1000
x10(2) x100(2) x1000(2)
Swift实现
这里不考虑大数,仅作为思路展示
三、 解题
本题的条件与上面介绍的快速幂中的例子略有不同,调整一下即可。
3.1 递归
3.2 非递归
Last updated