java - BigInteger 上的操作有多复杂？

Question

目前BigInteger中的multiply、divide和pow方法的复杂度如何？文档中没有提及计算复杂性(其他任何地方也没有)。

Answer 1

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

注意:这是针对 Java 6 的。我认为它在 Java 7 中不会有什么不同。