Пространственная сложность для простого алгоритма потоковой передачи

Question

Я хочу определить сложность пространства и перейти к примеру простого алгоритма потоковой передачи.

Если вы получаете перестановку из n-1 разных чисел и должны обнаружить одно пропущенное число, вы вычисляете сумму всех чисел от 1 до n по формуле n (n + 1) / 2, а затем вычитаете каждое входящее число. В результате ваш пропущенный номер. Я нашел статью из немецкой википедии, в которой говорится, что сложность этого алгоритма в пространстве равна O (log n). ( https://de.wikipedia.org/wiki/Datenstromalgorithmus)

Что я не понимаю: количество бит, необходимое для хранения числа n, равно log2(n). хорошо.. но я должен рассчитать сумму, жестко. Таким образом, n (n + 1) / 2 больше, чем n, и поэтому требует больше места, чем просто log (n), верно?

Может кто-то помочь мне с этим? Заранее спасибо!

Answer 1

Если целое число A в двоичном кодировании требует N_a бит, а целое число B требует N_b бит, тогда A*B требует не более N_a+ N_b бит (не N_a * N_b). Таким образом, для выражения n(n+1)/2 требуется не более log2(n) + log2(n+1) = O(2log2(n)) = O(log2(n)) битов.

Более того, вы можете поднять n к любой фиксированной мощности i и он по-прежнему будет использовать пространство O (log2 (n)). n Для самого n¹⁰, n⁵⁰⁰, n^10000000 требуется O(log(n)) битов памяти.