算法 - How to prove the expected number of probes in Open addressing

问题描述

问 题

The outline of my following content

• background

• question

1.background

• theorem 11.6 and Proof process

• questions

questions in the background

(1) my first question is why Pr{X>=i} but not Pr{X==i} ?

(2) my second question is Why Pr{A1} = n/m ?

I have some thought for question(2) in my figure.

解决方案

你的第二的问题挺显然的，第一次就撞上被占用格子的概率就是load factor（n/m）啊。

第一个问题把m,n换成具体的数字就好理解了。比如100个格子里面占用了10个，空闲90个：

$$\array{Pr\{X \geq 3\} = Pr\{\text{前两次都撞到占用}\} \\\qquad = \frac{10}{100} \cdot \frac{9}{99}}$$

不同于

$$\matrix{Pr\{X = 3\} = Pr\{\text{前两次都撞到占用，第三次撞到空闲}\} \\= \frac{10}{100} \cdot \frac{9}{99} \cdot \frac{90}{98}}$$

这篇关于算法 - How to prove the expected number of probes in Open addressing的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！