Comments 21
Теперь, зная степени всех простых делителей n≀, у нас есть способ вычисления swinging factorial.
С какой сложностью нам достается это знание?
Простых чисел от 1 до n всего O(n / log n), вычисление lp происходит за O(log n).
Сложностью же перемножения простых чисел в соответствующих степенях будет O(n (log n)2 log log n) — это уже не очевидная оценка, её доказательство есть по второй ссылке.
Я правильно понимаю, что придется хранить или генерировать таблицу простых чисел от 2 до n/2?
Какова трудоемкость детерминированного алгоритма теста на простоту?
Не совсем, понадобится таблица простых чисел от 2 до n.
Решето Эратосфена составляется за O(n * log log n), это меньше, чем время вычисления факториала. Отдельного способа проверки на простоту алгоритм не требует.
array[0, 1, 2, 6, 24, 120, ...]
Простите за серость, а зачем нужно вычислять большие факториалы? Криптография? Комбинаторика? Ряды Тейлора? Собеседование в Гугл?
Боюсь, что это вопрос не ко мне. Вероятнее всего различные алгоритмы вычисления факториала имеют соревновательный характер.
Хранить массив может быть очень затратно по памяти, особенно если нужны значения порядка 1000000! (вдруг они кому-то нужны). На практике я такого не встречал и сам всегда хранил кэшированные значения в обычном массиве (во время решения задач по программированию).
Несмотря на то, что формально перемножение чисел от 1 до n имеет ту же трудоёмкость, алгоритм PrimeSwing на практике оказывается самым быстрым.
Предположим, что разделим числа на две половины, рекурсивно вычислим произведение и перемножим половины. Сложность у этого метода ~M(n*log(n))*log(n), что хуже ~M(n*log(n)) у PrimeSwing. Или как предлагается перемножать?
Метод Шёнхаге — Штрассена считался асимптотически быстрейшим методом с 1971 до 2007 годы, пока не был заявлен новый метод с лучшей оценкой сложности умножения.[3] На практике метод Шёнхаге — Штрассена начинает превосходить более ранние классические методы, такие как умножение Карацубы и алгоритм Тоома — Кука (обобщение метода Карацубы), начиная с целых чисел порядка 10^10000-10^40000.
Таким образом становится актуальным вопрос о константе в оценке.
Если я верно понял, автор производил вычисления факториалов примерно до 1000000, то есть результаты были не настолько большими, чтобы использовать Алгоритма Фюрера (если верить википедии). А так да, теоретическую оценку наверняка можно улучшить.
На практике я не заморачивался и использовал то умножение, какое было реализовано за меня в BigInteger.
Спасибо за замечание.
Зачем считать для цешек факториалы, если есть треугольник паскаля?
Я могу оценить время на генерацию N строк как O(N^3).
В Вашем случае (N = 300) — пара минут максимум.
Быстрое вычисление факториала — PrimeSwing