Big-O Espace requis pour la multiplication

Question

Dépassement de pile. Je vois ici d'excellentes ressources sur la complexité temporelle, mais jusqu'ici je n'ai pas été capable de répondre à cette question de complexité spatiale en les utilisant. Donc:

Si je multiplie les n premiers nombres premiers ensemble, quel espace serait nécessaire pour stocker la réponse? Par exemple, multiplier les mille premiers nombres premiers et stocker le nombre résultant (un entier, quoique grand). Cela nécessiterait-il un espace n-carré ou log (n)?

Merci beaucoup!

Answer 1

Je prends juste la dernière partie de votre question. Si vous avez une liste des n premiers nombres premiers, le nombre de chiffres dans la multiplication finale sera log (n^n) qui est juste n log n. Puisque l'algorithme consisterait simplement à multiplier chacun avec un seul accumulateur, je dirais que l'espace total requis serait le nombre de chiffres final attendu, qui est: n log (n)

Answer 2

Le prime number theorem nous dit que le n ème premier est d'environ n en n, de sorte que le produit de la première n nombres premiers est d'environ

Π _{i ≤ n} (i ln i) = n! O ((log n) ⁿ) = O ((n log n) ⁿ)

Et pour représenter ce numéro, vous auriez besoin d'espace est la logarithme de cela, à savoir

O (n (log n + journal log n)).

(Notez que ceci est asymptotiquement plus grand que l'espace nécessaire pour stocker n!, Qui est juste O (n log n).)