jcm*_*jcm 5 algorithm big-o space-complexity
有人可以向我解释以下空间复杂度计算吗？
给定大小为b位的数量流,计算这些数字的总和.
如果到目前为止我们已经看到T数,则总和最多为T2 ^ b,因此最多需要O(b + log T)空间.
现在,T2 ^ b必须是上限,因为更准确的上限将是T(2 ^ b - 1).
但他们是如何计算出空间上限是O(b + logT)？
使用m位,您可以存储最多(约)2 米的数字.因此,以另一种方式工作,如果您知道总和,则需要使用对数来获取位数(因此空间复杂度).
这里,log(T 2 b)= b + log(T).
| 归档时间： |
|
| 查看次数： |
65 次 |
| 最近记录： |