乘法的 Big-O 空间要求
堆栈溢出。我在这里看到了一些关于时间复杂性的优秀资源，但到目前为止我还无法使用它们来回答这个空间复杂性问题。那么：
如果我将前 n 个素数相乘，需要多少空间来存储答案？例如，将前一千个素数相乘并存储结果数字（一个整数，尽管很大）。需要 n 平方或 log(n) 空间吗？
非常感谢！
Stack Overflow. I see some great resources on time complexity here, but so far I haven't been able to answer to this space complexity question using them. So:
If I am multiplying the first n primes together, what space would be required to store the answer? For example, multiplying the first thousand primes together and storing the resulting number (an integer, albeit a large one). Would it require n-squared or log(n) space?
Thanks so much!
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
素数定理告诉我们，第n个素数约为< em>n ln n，因此前 n 个素数的乘积大约为
为了表示这个数字，你需要空间，即它的对数，即
（请注意，这渐近大于存储 n！ 所需的空间，即 O(n log n)。）
The prime number theorem tells us that the nth prime is approximately n ln n, so the product of the first n primes is approximately
And to represent this number you'd need space that's the logarithm of that, i.e.
(Note that this is asymptotically bigger than the space needed to store n!, which is just O(n log n).)
只是回答你问题的最后一部分。如果您有前 n 个素数的列表，则最终乘法中的位数将是 log(n^n)，即 n log n。由于该算法只是将每个数字与单个累加器相乘，因此我认为总空间需求将是最终预期的数字位数，即： n log(n)
Just taking the last part of your question. If you have a list of the first n primes, the # of digits in the final multiplication will be log(n^n) which is just n log n. Since the algorithm would just be to multiply each one with a single accumulator, i would say the total space requirement would be the final expected # of digits, which is: n log(n)