跳过列表:列表的最大级别大于 k 的概率

Question

给定 randomLevel(( 函数：

enter code here
randomLevel()
    newLevel := 1
        --random() returns a random value in [0,1)
    while random() < p do
        newLevel := newLevel+1
    return min(newLevel,MaxLevel)

这用于确定在插入节点时他将获得什么级别，根据 Pugh 的文章，列表的最大级别大于 k 的概率等于 1 - (1 - p^k (^n，文章还说这个表达式最多是 np^k(因此预期的最大水平最多为 L(n( + 1/(1-p(， 对于那些知道这篇文章的人..(。

我在理解这个数字的来源方面遇到了严重的麻烦，因为我能想到的是 P(级别 j 中的节点(= (p^j((1-p( => P(级别大于 k 的节点(= 1 - sum(P(级别 i 中的节点(，i=1 到 i=k(，这比导致P(最大级别> k( = P(级别> k 中的一个节点( = n P(级别大于 k 的节点( = ... = n*(1+p*(p^k-1((

帮助???谢谢:)

Answer 1

考虑一下

，使用 p = 0.5 ，你有：

1/2 of the nodes at level 1
1/4 of the nodes at level 2
1/8 of the nodes at level 3
1/16 of the nodes at level 4
etc.

节点处于级别 k 的概率是节点处于级别 k-1 的概率的 1/2。

或者，使用您发布的符号：

P(node in level greater than k) = 1 - sum(P(node in level i), i=1 to i=k)

因此，节点处于大于 4 的水平的概率例如为：

= 1 - (1/2 + 1/4 + 1/8 + 1/16)
= 1 - (8/16 + 4/16 + 2/16 + 1/16)
= 1 - 15/16
= 1/16