堆栈溢出。我在这里看到了一些关于时间复杂度的重要资源，但到目前为止，我还无法使用它们来回答这个空间复杂度问题。所以：
如果我将前 n 个素数相乘，存储答案需要什么空间？例如，将前一千个素数相乘并存储结果数（一个整数，尽管很大）。它需要 n 平方或 log(n) 空间吗？
非常感谢！
问问题
607 次
2 回答
1
素数定理告诉我们第n个素数大约是n ln n，所以前n 个素数的乘积大约是
Π我≤ n (我ln我) = n！O((log n ) n ) = O(( n log n ) n )
为了表示这个数字，你需要空间，这是它的对数，即
O( n (log n + log log n ))。
（请注意，这比存储n ! 所需的空间渐进地大，它只是 O( n log n )。）
于 2010-12-08T00:02:47.867 回答
0
只是回答你问题的最后一部分。如果您有前 n 个素数的列表，则最终乘法中的位数将是 log(n^n)，即 n log n。由于该算法只是将每个累加器与单个累加器相乘，因此我会说总空间需求将是最终预期的位数，即：n log(n)
于 2010-12-07T23:47:49.570 回答