Big-O Пространство для умножения

Question

Переполнение стека.Я вижу здесь большие ресурсы по сложности времени, но до сих пор я не смог ответить на этот вопрос о сложности пространства, используя их.Итак:

Если я умножу первые n простых чисел, какое пробел потребуется для хранения ответа?Например, умножение первой тысячи простых чисел вместе и сохранение полученного числа (целое число, хотя и большое).Требуется ли n-квадрат или лог (n)?

Большое спасибо!

Answer 1

Теорема простого числа говорит нам, что n th простое число приблизительно равно n ln n , так что произведение первого n простых чисел приблизительно

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

И для представления этого числа вам понадобится пробел, который является логарифмом этого, то есть

O ( n (журнал n + журнал n )).

(Обратите внимание, что это асимптотически больше места, необходимого для хранения n !, что составляет всего O ( n log n ).)

Answer 2

Просто отвечу на последнюю часть вашего вопроса.Если у вас есть список первых n простых чисел, число цифр в конечном умножении будет log (n ^ n), которое равно n log n.Поскольку алгоритм просто должен был бы умножить каждый из них на один аккумулятор, я бы сказал, что общее требование к пространству будет заключительным ожидаемым числом цифр, которое равно: n log (n)