跳錶：</p> <pre><code>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) </code></pre> <p>這是用來確定在什麼樣的水平，他將一個節點插入：該列表的最大水平比給出的randomLevel（）函數K

Question

更大的概率根據pugh的文章，獲得列表的最大級別大於k的概率等於1-（1-p^k）^ n，並且文章還稱該表達式最多爲np^k（因此對於那些瞭解這篇文章的人來說，預期的最大水平至多爲L（n）+ 1 /（1-p）..）。因爲所有我能想到的是P（節點j級）=（p^j）（1-p）=> P（節點（等級大於k）= 1 - 和（P（在等級i中的節點），i = 1到i = k），其導致P（最大等級> k）= P（等級> k中的一個節點） = n P（節點電平大於k）= ... = n *（1 + p *（p^k-1））

help ???謝謝:)

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級節點的概率爲1/2的節點是在k-1水平的概率。

或者，使用您發佈的註釋：

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