java - 计算阶乘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 的数字。