Доброго времени суток!
Сегодня я решил порешать простую с виду задачу: всего лишь посчитать факториал числа n
Однако столкнулся с той трудностью, что не могу это сделать за что-либо более быстрое, чем O(n^2logn)(хотя мне кажется, что у меня есть идея чего-то похожего на метод разделяй и властвуй за O(nlog^3n), но я не уверен)
Собственно мне интересно, за сколько можно решить эту задачу:) Буду рад услышать любые асимптотически более быстрые решения, чем O(n^2logn)
Тык
Я, несомненно, это читал, прежде чем задать вопрос:)
Моя идея за nlog^3n похожа на описанный метод с деревом, однако я не способен адекватно оценить, за сколько это будет асимптотически работать — там указано очень неправдоподобное утверждение про то, что произведение чисел от L до M примерно равно произведению чисел от M до R.
А метод с разложением на простые множители как я понимаю работает за те же O(n^2logn) из-за необходимости в конце перемножить ответы по простым.
Если сделать random_shuffle для всех n чисел, то произведения на (L,M) и (M+1,R) будут примерно равны и тогда будет O(nlog^3n).
Всё таки O(nlog^3n), если умножать Фурье( так как в n! ~ n * logn цифр). Собственно это и было моей идей, только не random_shuffle,а перемножение двух самых маленьких по числу цифр чисел каждый раз:) Интересует, можно ли как-нибудь быстрее, скажем без рекурсии за что-нибудь вроде nlog^2n
Таки да, O(nlog^3n), насколько я знаю быстрее вроде ничего нет, кроме random_shuffle + фурье + разделяй и властвуй, попробуйте оптимизировать фурье.
Ясно, жаль, спасибо за ответ.
(наверное, меня за такие слова здесь закидают помидорами:)) Меня это вопрос заинтересовал с теоретической точки зрения — никакого практического подтекста или задачи с какого-нибудь контеста за этим не стоит
А за что закидают? Спортивные программисты по своей сути уже теоретики, потому что занимаются вещами, редко применимыми в промышленном программировании :)
Можно все числа скинуть в кучу и выбирать постоянно 2 наименьших по длине. Помню была задача с Петрозаводска, где надо было посчитать 40000!, авторское решение было таким.
Я придумал именно это, только не до конца понимал, почему это работает быстро