5

插入 n 个元素后，跳过列表使用的预期空间是多少？

我预计在最坏的情况下，空间消耗可能会无限增长。

维基百科说“空间 O(n)”。

如何以一种或另一种方式证明这一点？

4

3 回答 3

4

根据这篇我觉得比维基百科更可靠的论文，维基百科是错误的。概率跳过列表是Theta(nlogn)最坏情况下的空间复杂度。

尽管 PSL 的平均性能相当不错，但在最坏的情况下，它的 Theta(n lg n) 空间和 Theta(n) 时间复杂度高得无法接受

最坏的情况不是无限的，因为您可以将自己限制f(n)在列表的数量、位置f(n) = O(logn)，并在达到此高度时停止抛硬币。所以，如果你有f(n)完整的行，你会得到O(nlogn)节点总数，因此这种情况下的空间复杂度是O(nlogn)，而不是O(n)。

编辑：
如果您正在寻找预期的空间消耗，而不是问题中最初陈述的 最糟糕
的情况，那么：让我们将“列”表示为底部节点，并将所有节点“向上”表示为它。

E(#nodes) = Sigma(E(#nodes_for_column_i)) (i in [1,n])

上述等式是正确的，因为期望值是线性的。

E(#nodes_for_column_i) = 1 + 1/2 + ... + 1/n < 2（对于每个 i）。这是因为概率为 1 它有 1 个节点，当 p=1/2 时，每个节点都有一个额外的节点。当 p'=1/2 时，它们中的每一个都有一个额外的节点 (total p*p'=1/4) ,.... 因此我们可以得出：

E(#nodes) = n*E(#nodes_for_each_column) = n*(1+1/2+...+1/n) < 2n = O(n)
于 2012-05-06T15:27:07.070 回答
0

让我们有一个具有 N 个节点的确定性跳过列表。除了数据值，列表还包含：

1 级有 N 个指针，2 级有 N/2 个指针，3 级有 N/4 个指针，依此类推……

N + N/2 + N/4 + N/8 +..N/2^k 是几何级数之和，其极限是2N，所以最大内存消耗是N*SizeOf(Data) + 2*N*SizeOf （指针）= O(N)。

我没有考虑到层间链接，但它们的数量大约是指针数量。

于 2012-05-06T15:27:23.007 回答
0

预期空间复杂度

跳过列表具有logn层。跳过列表中的每个元素都出现在一个或多个层中。为了测量跳过列表的预期空间复杂度，我们可以评估任意元素 x 出现的预期层数。

我们知道 x 有 100% 的几率只出现在最底层，有 50% 的几率出现​​在最底层和最底层的 2 层，有 25% 的几率出现​​在最底层的 3 层，有 12.5% 的几率出现在底部 4 层，依此类推。

在数学上，我们可以表示 x 出现的预期层数如下......

Sum(i / 2^(i-1)) from i=1 to logn

... ix 可能出现的层数在哪里。

直观地，我们可以看到上述总和收敛到一个常数，因为分母的增长速度比分子快得多。您可以通过将方程代入 Wolfram Alpha 来验证这一点（对于非常大的 n 值，总和收敛到 4）。这意味着...

[Sum(i / 2^(i-1)) from i=1 to logn] = O(1)

因此，我们已经证明在任意跳过列表中存储任意元素平均需要恒定空间。为了获得在跳过列表中存储n元素的空间复杂度，我们只需乘以n.

n*O(1) = O(n)

因此，跳过列表具有线性预期空间复杂度。

最坏情况下的空间复杂度

这实际上要容易得多。我们知道有logn层次和n元素。在最坏的情况下，每个元素都在每一层中。因此，O(nlogn)。

于 2018-07-01T17:18:10.287 回答