Какова временная сложность вычисления факториала n!используя Java BigInteger - PullRequest
Новая
       30

Какова временная сложность вычисления факториала n!используя Java BigInteger

0 голосов
/ 07 марта 2019

Предположим, что алгоритм выглядит следующим образом: 

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

1 Ответ

1 голос
/ 07 марта 2019

Количество цифр в fact равно log(fact). Можно показать , что 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 использует умножение Карацубы, умножение Тоом-Кука или, возможно, даже алгоритм Шёнхаге-Штрассена.Я не знаю, как они работают с целыми числами таких резко различающихся размеров (logn против nlogn), поэтому я не могу дать точную верхнюю границу для них.Лучшее, что я могу сделать, - это предположить, что оно будет меньше, чем у O(n*F(nlogn)), где F(x) - время умножения двух чисел длины x с использованием определенного алгоритма.

...