1

所以我在学校一直在研究跳过列表，我们简要讨论了如果我们要在跳过列表中使用“不公平硬币”而不是公平硬币，（例如：不公平硬币翻转导致值“ Heads”设置为 p，其中 0 < p < 1（因此“Tails”的概率为 1 -p）。

由于我们这么快就跳过了这个话题，所以我对此有些疑惑，但我并不真正理解。

  1. 如果我们这样做，跳过列表的高度/大小会发生什么变化？如果概率出现偏差，这显然会改变事情，对吧？假设它包含任意 n 个元素，显然高度会与我们使用公平硬币不同。

  2. 将任意节点添加到跳过列表时，预期的促销数量将如何变化？我不知道在这种情况下是否会这样，但这是一个讨论话题。

我不是在找人在没有我真正理解的情况下给出答案，但如果你能真正解释为什么会发生这些变化，以便我能理解它是如何受到概率变化的影响的，我将不胜感激。

编辑：我想我在将不同概率与 Pat Morin 的《开放数据结构》一书第 99 页提供的方程式进行了一些比较后现在理解了。一旦我弄清楚了，我会在评论中发布我的解决方案，以帮助其他人解决同样的问题。

4

1 回答 1

0

您可以在此处查找您的问题的答案：https
://en.wikipedia.org/wiki/Skip_list#Description 我将尝试解释它们：
设 p 是一个元素被提升到下一个级别的概率，然后

  1. 高度将为log 1/p n。
    原因：
    在最后一行 0 我们有 n 个元素。由于每个元素都有p出现在下一个较高行的概率，所以我们在第 1 行有n * p 个元素。同样的争论，我们将在第 2 行得到n * p 2 个元素。如您所见，我们有n *行x中的p x 个元素。
    最高行将有 1 个项目，因此我们得到等式1 = n * p x并求解x我们得到x = log 1/p n（x = log 2 n表示公平硬币）。
  2. 每个元素平均出现在1/(1-p) 个列表中。
    原因：
    只出现在一个列表中的机会是(1 - p)（晋升机会是p）。
    进入第二个但不是第三个列表的机会是p * (1 - p)（提升一次 [ p ] 而不是在第二次抛硬币 [ 1-p ] 时）。
    第二个但不是第三个p 2 * (1 - p)等等
    一般来说：
    p x-1 * (1-p)用于在x列表中。
    对于列表中出现的元素的期望值，我们有：
    exp = 1 * (1-p) + 2 * p * (1-p) + 3 * p2 * (1-p) ...
    = ∑ i=0 ∞ (i+1) * p i * (1-p)
    = (1-p) * ∑ i=0 ∞ (1+i) * p i
    = (1-p) * 1/(1-p) 2
    = 1/(1-p)
    消除总和为1/(1-p) 2的证明可在此处找到： https://en。 wikipedia.org/wiki/Geometric_series#Geometric_power_series
于 2015-11-23T01:20:04.327 回答