java - 计算阶乘n的时间复杂度是多少!使用Java的BigInteger

假设算法如下：

public static BigInteger getFactorial(int num) {
    BigInteger fact = BigInteger.valueOf(1);
    for (int i = 1; i <= num; i++)
        fact = fact.multiply(BigInteger.valueOf(i)); // ? time complexity
    return fact;
}

似乎很难计算出事实的位数。
优化版本：

    public BigInteger getFactorial2(long n) {
        return subFactorial(1, n);
    }
    private BigInteger subFactorial(long a, long b) {
        if ((b - a) < 10) {
            BigInteger res = BigInteger.ONE;
            for (long i = a; i <= b; i++) {
                res = res.multiply(BigInteger.valueOf(i));
            }
            return res;
        } else {
            long mid = a + (b - a) / 2;
            return subFactorial(a, mid).multiply(subFactorial(mid + 1, b));
        }
    }

最佳答案

fact中包含的位数为log(fact)It can be shown表示O(log(n!)) == O(nlogn)，因此n!中的位数与nlogn成比例增长由于您的算法将值堆积到一个部分积上，而不将它们分割成较小的中间值（分而治之的方式），因此我们可以断言，要计算n时，要乘以的一个数字将小于n!。使用小学乘法，我们有O(logn * nlogn)时间来乘这些数，我们有n-1乘法，所以这是O(n * logn * nlogn) == O((nlogn)^2)。我相信这是一个严格的小学乘法上限，因为即使开始的乘法要小得多，但后一半都大于O((n/2)log^2(n/2))，而且有(n/2)的乘法，所以O((n/2)^2 *log^2(n/2)) == O((nlogn)^2)。
然而，完全有可能BigInteger使用karatsuba乘法、toom-cook乘法，甚至可能使用schónhage–strassen算法。我不知道它们是如何在大小变化如此之大的整数上执行的（lognvsnlogn），所以我不能给出它们的严格上限。我能做的最好的推测是它将小于O(n*F(nlogn))，其中F(x)是使用特定算法乘以两个长度x的时间。

关于java - 计算阶乘n的时间复杂度是多少!使用Java的BigInteger，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/55037260/