Java 7的BigInteger操作有多复杂？
目前BigInteger中的方法有多大的复杂性， divide和pow ？ 没有提到文档中的计算复杂性（也没有提到其他任何地方）。
如果你看一下BigInteger的代码（随JDK提供），我觉得multiply(..)有O（n ^ 2） （实际上这个方法是multiplyToLen(..) ）。 其他方法的代码有点复杂，但你可以看到自己。
注意：这适用于Java 6.我假设它在Java 7中没有区别。
测量它。 使用线性增加操作数进行操作并在图上绘制时间。 不要忘记预热JVM（多次运行）以获得有效的基准测试结果。
如果操作是线性O（n），则二次O（n ^ 2），多项式或指数应该是显而易见的。
编辑：虽然你可以给算法理论界限，但它们在实践中可能不那么有用。 首先，复杂性并没有给出因素。 一些线性或子二次算法根本没用，因为它们吃了太多的时间和资源，以至于它们不适合手头的问题（例如Coppersmith-Winograd矩阵乘法）。 然后你的计算可能有你只能通过实验检测到的所有kludges。 有一些准备算法无法解决问题，但可以加速真正的求解器（矩阵调节）。 有一些次优的实现。 如果长度较长，速度可能会急剧下降（缓存丢失，内存移动等）。 所以出于实际目的，我建议做实验。
最好的方法是每次输入的长度加倍并比较时间。 是的，您确实发现算法是否具有n ^ 1.5或n ^ 1.8复杂度。 只需将输入长度增加四倍，您只需要1.5的半个时间而不是2.如果将长度乘以256次，则再次获得1.8的时间。
有一个新的“更好”的BigInteger类没有被sun jdk用于保守主义和缺乏有用的回归测试（庞大的数据集）。 做出更好算法的人可能会在评论中讨论过旧的BigInteger。
在这里你去http://futureboy.us/temp/BigInteger.java