Расчет большой факторной сложности времени
Я столкнулся с проблемой, когда мне нужно было вычислить значения очень больших факториалов. Я решил эту проблему в C ++ двумя различными способами, но хочу знать только, насколько точен мой анализ сложности.
В любом методе я представляю очень большие числа как векторы, где v[0] представляет наименее значимую цифру, а значение в последнем индексе представляет наиболее значимую цифру. Код версии 1 можно найти в этом суть.
Учитывая приведенный выше код, кажется, 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) раз где 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() существует в этом суть. Использует функцию 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!
Выписывание полного суммирования теперь должно дать:
Похоже, асимптотическая сложность обоих методов одинакова, учитывая, что мои вычисления точны. Это правда?
Решение
Сложность функции в суть вы предоставили O(log10n!), где 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)!, то есть он содержит все цифры, которые составляют это число. Однако длина этого числа просто ⌈log10((n-1)!)⌉, Вы можете увидеть это на простом примере:
если (n-1)! составляет 100, то длина numVector будет 3, что так же, как ⌈log10100⌉ = 3,
Та же логика применима и к циклу while:
while (carry) {
returnVec.push_back(carry%10);
carry /= 10;
}
Поскольку значение carry не будет больше чем n (вы можете доказать это для себя), тогда максимальное количество раз, когда этот цикл будет выполняться, также не будет больше, чем ⌈log10n!⌉, тогда общая сложность функции эквивалентна O(log10n!),
Поэтому для расчета k!, сложность вашего кода (включая основной) будет O(klog10k!)
Наивная версия
Для наивной версии единственное, что изменилось, — это то, что теперь метод вручную выполняет умножение в форме сложения. Это то, что пропустила другая версия, явно умножив каждое значение на n
(numVector[i]*n + carry)
Это увеличивает сложность функции до O(klog10n!), где k! = n и, следовательно, сложность всего кода теперь O(k2log10k!)
Другие решения
Умножение числа k-цифр на целое число или добавление двух чисел k-цифр требует времени, пропорционального k.
Следовательно, в многократной версии общая нагрузка
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)
Как и следовало ожидать, есть дополнительный n фактор.