BigInteger上的操作有什么复杂性? [英] What complexity are operations on BigInteger?

问题描述

BigInteger中的方法multiply，divide和pow目前有什么复杂性?在文档中(也没有其他地方)没有提到计算复杂性.

What complexity are the methods multiply, divide and pow in BigInteger currently? There is no mention of the computational complexity in the documentation (nor anywhere else).

推荐答案

如果您查看BigInteger的代码(由JDK提供)，在我看来 multiply(..)具有 O(n ^ 2)(实际上是multiplyToLen(..)).其他方法的代码稍微复杂一些，但是您可以自己看看.

If you look at the code for BigInteger (provided with JDK), it appears to me that multiply(..) has O(n^2) (actually the method is multiplyToLen(..)). The code for the other methods is a bit more complex, but you can see yourself.

注意:这是针对Java 6的.我认为它与Java 7相同.

Note: this is for Java 6. I assume it won't differ in Java 7.

这篇关于BigInteger上的操作有什么复杂性?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！