0

我想确定 go to 简单流式算法示例的空间复杂度。

如果您得到 n-1 个不同数字的排列并且必须检测一个缺失的数字，您可以使用公式 n (n + 1) / 2 计算所有数字 1 到 n 的总和，然后减去每个传入的数字。结果是您丢失的号码。我发现一篇德国维基百科文章指出该算法的空间复杂度为 O(log n)。（https://de.wikipedia.org/wiki/Datanstromalgorithmus）

我不明白的是：存储一个数字 n 所需的位数是 log2(n)。好的..但我必须计算总和，很难。所以 n (n + 1) / 2 比 n 大，因此需要比 log (n) 更多的空间，对吧？

有人可以帮我弄这个吗？提前致谢！

4

1 回答 1

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 10， n 500， n 10000000都需要 O(log(n)) 位存储。

于 2016-06-27T15:26:49.250 回答