求这段大数阶乘算法的时间复杂度和空间复杂度
利用bigInteger实现了一下大数阶乘的算法，实测比直接迭代相乘快一个数量级，但是不知道怎么求时间和空间复杂，想大家帮忙看下。
private static String factorial(int n) {
java.math.BigInteger ans = java.math.BigInteger.valueOf(1);
int bits = 0;
for (int i = 2; i <= n; i++) {
if (Integer.bitCount(i) == 1) {
bits += Integer.numberOfTrailingZeros(i);
continue;
}
// ans = ans.multiply(java.math.BigInteger.valueOf(i));
}
ans = subFactorial(1, n);
return ans.shiftLeft(bits).toString();
}
private static java.math.BigInteger subFactorial(long a, long b) {
if ((b - a) < 10) {
java.math.BigInteger res = java.math.BigInteger.ONE;
for (long i = a; i <= b; i++) {
if (Long.bitCount(i) == 1) {
continue;
}
res = res.multiply(java.math.BigInteger.valueOf(i));
}
return res;
} else {
long mid = a + b >>> 1;
return subFactorial(a, mid).multiply(subFactorial(mid + 1, b));
}
}如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
教你个简单粗暴的办法 - 计数法：
输出
可见 count/i 几乎是常数，所以时间复杂度应是： O(n)
空间复杂度可以通过分配内存测量， 因为是用的二分法， n每增加一, 栈多一层，应该是O(log n ).
根据 @fefe 的补充，和这里的讨论 https://stackoverflow.com/que... 可以看出大数乘法多采用适应性的混合算法，就是算小数和大数时用的算法不太一样，但基本是小于O(n^2)的， 好一些的在O(n^1.5)左右。取大原则， 最终在算法时间复杂度也是由大数乘法决定的。