Вычисление большой факториальной временной сложности

Я столкнулся с проблемой, когда мне нужно было рассчитать значения очень больших факториалов. Я решил эту проблему на С++ двумя разными способами, но хочу знать, действительно ли мой анализ сложности.

В любом из методов я представляю очень большие числа в виде векторов, где v[0] представляет наименее значащую цифру, а значение последнего индекса представляет собой наиболее значимую цифру. Код версии 1 можно найти в этом gist.

Учитывая приведенный выше код, кажется, что multiplyVectorByInteger() есть O(log(n*k)), где n - заданное целое число, а k - это число, представленное вектором. Моя логика заключается в том, что мы будем делать несколько шагов пропорционально длине результирующего числа n*k, чтобы создать вектор, представляющий n*k. Длина n*k равна O(log(n*k)) Некоторые из шагов будут выполняться в цикле for, другие - в цикле while.

В этой программе для поиска больших факториалов, всякий раз, когда мы называем multiplyVectorByInteger(), мы будем передавать целое число n и векторное представление (n-1)!. Это означает, что если мы хотим найти 6!, мы передадим целое число 6 и векторное представление 5!. Функция вернет векторное представление 6!. Используя предыдущую информацию, я считаю, что сложность - это O(log(i!)), где я - это переданное целое число. Чтобы найти большие факториалы, мы должны назвать этот метод O(n) times, где n - факториал, который мы пытаемся найти. Наша накопленная логика будет выглядеть так:

1!       = 1!
1!*2     = 2!
2!*3     = 3!
3!*4     = 4!
...
(n-1)!*n = n!

Так как на каждом уровне мы вычисляем i!, мы последовательно выполняем шаги O(log(i!)) на каждом уровне. Суммирование, чтобы показать это, выглядит следующим образом:

Моя логика от перехода от второго суммирования к нотации Big-Oh выглядит следующим образом: нарушая это, получаем следующее:

1log(1) + 2log(2) + 3log(3) + ... + nlog(n)

Очевидно, что мы получаем O(n^2) члены log(1) + log(2) + ... + log(n). Правила журнала напоминают нам, что log(a) + log(b) = log(ab), что означает, что члены журнала в этом случае сворачиваются на log(n!). Таким образом, имеем O(n^2)log(n!).

Это создаст общую временную сложность этой программы O(n^2log(n!)). Правильно ли этот анализ?

Максимальная временная сложность версии

Чтобы анализировать сложность, я хочу взглянуть на то, что кажется менее эффективным решением. Предположим, мы изменили нашу функцию multiplyVectorByInteger() так, чтобы вместо умножения векторного представления k на целое число n в O(log(n!)) времени для создания n!, новая функция multiplyVectorByIntegerNaive() добавляет векторное представление числа вместе в общей сложности n раз.

multiplyVectorByIntegerNaive() существует в gist. В нем используется функция addVectors(), сложность которой O(n) где n размер большего из двух векторов.

Ясно, что мы по-прежнему вызываем эту новую функцию умножения n раз, но нам нужно увидеть, изменилась ли сложность. Например, учитывая целое число 6 и векторное представление 5!, добавим 5! + 5! + 5! + 5! + 5! + 5!, чтобы получить 6*5! = 6!. Если заданное целое число для нашей функции умножения i, то ясно, что мы делаем дополнения i-1. Мы можем перечислять шаги для предыдущего примера вызова нашей наивной функции умножения.

5! + 5!
2*5! + 5!
3*5! + 5!
4*5! + 5!
5*5! + 5!

Списание полного суммирования должно теперь давать:

Похоже, что асимптотическая сложность обоих методов одинакова, если мои вычисления точны. Это правда?

Ответы

for (int i = 0; i < numVector.size(); ++i) {
    returnVec[i] = (numVector[i]*n + carry) % 10;
    carry = (numVector[i]*n + carry) / 10;
}

while (carry) {
    returnVec.push_back(carry%10);
    carry /= 10;
}

Sum[i=1,n]: log(i!) ~  Sum[i=1,n]: i.log(i) ~ n²log(n)

Sum[i=1,n]: i.log(i!) ~ Sum[i=1,n]: i².log(i!) ~ n³.log(n)

Int x.log(x) dx = x²(log(x)/2 - 1/4)
Int x².log(x) dx = x³(log(x)/3 - 1/9)