スタックオーバーフロー。ここには時間計算量に関する優れたリソースがいくつかありますが、これまでのところ、それらを使用してこの空間計算量の質問に答えることはできませんでした。それで：
最初のn個の素数を掛け合わせる場合、答えを格納するためにどのようなスペースが必要になりますか？たとえば、最初の1000個の素数を乗算し、結果の数（大きいものではありますが整数）を格納します。n-squaredまたはlog（n）スペースが必要ですか？
本当にありがとう！
2 に答える
1
素数定理は、n番目の素数はおよそn ln nであることを示しているため、最初のn素数の積はおよそ
Π i ≤ n ( i ln i ) = n ! O((log n ) n ) = O(( n log n ) n )
そして、この数値を表すには、その対数であるスペースが必要です。
O( n (ログn + ログ ログn ))。
(これは、 n !を格納するために必要なスペースよりも漸近的に大きいことに注意してください。これは、ちょうど O( n log n ) です。)
于 2010-12-08T00:02:47.867 に答える
0
質問の最後の部分を取り上げるだけです。最初のn個の素数のリストがある場合、最後の乗算の桁数はlog（n ^ n）になります。これはちょうどnlognです。アルゴリズムはそれぞれを単一のアキュムレータで乗算するだけなので、必要な合計スペースは最終的に予想される桁数、つまりn log（n）になります。
于 2010-12-07T23:47:49.570 に答える