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

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

В любом из методов я представляю очень большие числа в виде векторов, где 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!

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

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

Ответ 1

Сложность функции в представленном вами значении O(log₁₀n!), где n - это номер, который вы передаете методу.

Обоснование этого очевидно из первой части кода:

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

Переданный numVector представляет (n - 1)!. т.е. содержит все цифры, составляющие это число. Однако длина этого числа просто ⌈log₁₀((n-1)!)⌉. Это можно увидеть на простом примере:

если (n-1)! равно 100, тогда длина numVector будет 3, которая будет такой же, как ⌈log₁₀100⌉ = 3.

То же самое относится и к циклу while:

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

Так как значение carry не будет больше, чем n (вы можете это доказать самостоятельно), то максимальное количество раз, в течение которого этот цикл будет работать, также не будет больше, чем ⌈log₁₀n!⌉, тогда общая сумма сложность функции эквивалентна O(log₁₀n!).

Поэтому для вычисления k! сложность вашего кода (включая main) будет O(klog₁₀k!)

Наивная версия

Для наивной версии единственное, что изменилось, это то, что теперь метод вручную переходит через умножение в форме сложения. Это то, что другая версия пропущена путем явного умножения каждого значения на n

(numVector[i]*n + carry)

Это увеличивает сложность функции до O(klog₁₀n!), где k! = n и, следовательно, сложность всего кода теперь O(k²log₁₀k!)

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

Ответ 1

Наивная версия

Ответ 2