BAT面试题43：log(n)时间复杂度下求n次幂
面试中，守望老铁遇到过在log(n)时间复杂度下求 a^b的问题。如何分析呢？
守望老铁此篇文章的博客地址为：
https://blog.csdn.net/weixin_42292229/article/details/86742650
精彩内容
这样划分，我们只要求
的值就可以的通过一次乘法运算求出
，依次求出，这就是快速幂，这样的操作的时间复杂度仅为O(logb)
代码如下，需要注意a和b可能为负数的问题。
1public double quickPow(long a,long b) {
2 //在此，定义0的0次幂为1
3 long tmpb=b;
4 if(b<0) tmpb=-b;
5 long s=1;
6 while(tmpb!=0){
7 if(tmpb%2==1)
8 s=s*a;
9
10 a=a*a;
11 tmpb/=2;
12 }
13 return b<0? 1.0/s:s;
14}本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。
原始发表：2019-02-06，如有侵权请联系 cloudcommunity@tencent.com 删除
本文分享自 程序员郭震zhenguo 微信公众号，前往查看
如有侵权，请联系 cloudcommunity@tencent.com 删除。
本文参与 腾讯云自媒体同步曝光计划 ，欢迎热爱写作的你一起参与！
评论
登录后参与评论
推荐阅读
腾讯云开发者
