Rhyme/冥运算(分治策略)Java版

冥运算(分治策略)Java版

算法原理

举个例子

我们求 X62=(X31)2
X31=(X15)2X
X15=(X7)2X
X7=(X3)2X
X3=(X)2X

我们以乘法的次数来作为运行时间的度量

先让我们来计算一下不使用分治策略计算X62需要的乘法次数为（62-1）次

使用分治策略之后的乘法次数为（2logN）

可见效率的提升是很明显的

冥运算算法的应用场景

应用场景有很多，典型的有密码学中的冥运算

程序代码

时间复杂度分析

T(N) = T(N/2)+logN

使用主分析法得T(N) = O(logN)