python - 如何降低Python中计算阶乘长度的程序的时间复杂度？

Question

我遇到了一个问题，我必须首先找到一个数字的阶乘，然后返回阶乘中获得的位数。我编写了该程序并且运行良好。但时间是 5.0015 秒，我必须在 1 秒内完成。如何减少这种情况？

下面是我的程序:

def factorial(n):
    fact = 1
    for y in xrange(1,n+1):
        fact = fact * y
    return fact

t = int(raw_input())
raw_input()
for x in xrange(t):
    n = int(raw_input())
    print len(str(factorial(n)))

Answer 1

利用数学的力量，避免完全计算阶乘。

数字的以 10 为底的对数是需要 10 的幂才能等于该数字。例如，math.log10(10) == 1、math.log10(11) == 1.0413926851582251、math.log10(100) == 2 等

这意味着最小整数严格大于某个数字的 log10(即，ceil(log10(n)) + (1 if log10(n).is_integer( ) else 0)) 是该数字中的位数。

此外，log10(a * b) = log10(a) + log10(b)。

这意味着log10(factorial(n)) == sum(log10(a) for a in range(1, n+1))

最后，该阶乘的长度为:

math.ceil(sum(math.log10(a) for a in xrange(1, n+1)))

(更多信息:http://en.wikipedia.org/wiki/Logarithm)