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

Question

假设算法如下：

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));
        }
    }

Answer 1

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算法。我不知道这些如何在如此大小不一的整数上表现出来（logn vs nlogn），所以我不能给出那些严格的上限。我能做的最好的是推测它将小于O(n*F(nlogn))，其中F(x)是使用特定算法乘以两个长度x的时间。