返回

数学心

首页
关灯
护眼
字体:
大
中
小
第九十章 牛顿快速幂
存入书签 我的书架 返回目录
亲爱的书友,您现在访问的是转码页面,可能导致更新不及时,访问最新更新请点击


顾名思义,快速幂就是快速算底数的n次幂。

    比如计算3的10此方,可以看到一下方法。

    普通计算就是:3^10=3*3*3*3*3*3*3*3*3*3

    可以变换为:3^10=(3*3)*(3*3)*(3*3)*(3*3)*(3*3)

    也就是先对3自己进行平方,再求五次,就是3^10=(3*3)^5,这就相当于求了5次乘法。

    最后可以变成先算3的平方,然后算其中五次,相当于只算了3次乘法。

    根据这个过程,可以得到其时间复杂度为O(logN),与朴素的O(N)相比效率有了极大的提高。

    其中用的是二分法。

上一章 目录 下一章