创建一个值为 `N!`（N 阶乘）的变量的函数的 space 复杂度是多少？

Question

整数值 N 的位长是 O(lgN)。

值 N! 的整数（即 N 阶乘）的位长是多少？如果函数在长度为 N 的列表中传递，并创建一个值为 N! 的变量，函数的 space 复杂度是多少？

示例函数：

def numPermutations(nums):
    '''Precondition: `nums` is a list of distinct numbers'''
    N = len(nums)
    return math.factorial(N)

该函数是否会具有 O(1) space 复杂性，因为它只创建一个整数变量（即 N）并且可以想象 math.factorial 的合理实现会也最多只创建几个整数变量？或者它会是 O(lgN!) 因为 N! 的位长大约是 lg2(N!)?

（旁注：lg2(N!) == 从 i = 1 到 N 的 lg2(i) 的总和。）

我编写了以下代码来创建一些数据：

from math import factorial

for N in range(100):
    print(f'{N}, {factorial(N).bit_length()}')

数据在此 Desmos 中可视化：Bit-length of N!。 Desmos 还包括一些与数据匹配的 functions/regressions。

Answer 1

根据 Stirling's formula，您可以假设 n! ~ c*sqrt(n)*n^n。因此，log(n!) ~ n*log(n)，即n!的space复杂度。

What is the space complexity of a function that creates a variable of value `N!` (N factorial)?