Java 中整数乘法的渐近复杂度是多少

Question

我对 int 类型、Integer 和 BigInteger 对象的乘法运算的渐近复杂性感兴趣：

int i,j = <value>;
i * j; // O?
Integer i,j = new Integer(<value>);  
i * j; // O?
BigInteger i,j = new BigInteger(<value>);
i.multiply(j); //O?

Answer 1

BigInteger.multiply 根据数字的大小使用多种算法。

小数使用naive算法O(n^2)

较大的数字使用Karatsuba算法O(n^1.585)

最大数使用Toom–Cook算法O(n^1.465)

我无法轻易确定用于确定使用哪种算法的数字长度阈值。如果您知道这一点，请编辑我的答案。

int乘法是O(1)因为整数(n)的大小是一个常数值