algorithm - 这个空间复杂度在这个级数和中是如何计算的？

Question

谁能给我解释一下下面的空间复杂度计算？

Given a stream of numbers of size b bits, calculate the sum of these numbers.

If we have seen T numbers so far, the sum is at most T2^b and hence needs at most O(b+log T) space.

现在，T2^b 必须是上限，因为更准确的上限是 T(2^b - 1)。

但是他们是如何计算出空间上界是O(b +logT)的呢？

Answer 1

使用 m 位，您可以存储最多(大约)2^m 的数字。因此，换句话说，如果您知道总和，则需要取对数以获得位数(以及空间复杂度)。

在这里，log(T 2^b) = b + log(T)。