平均检查数

Question

请考虑一组n个元素，其键值为 $$ 0,1，...，n-1。$$ 让 $ p（i）（0≤i≤n-1）$ 是搜索键的元素的概率。假设以下分发 $ p（i）$ ：

$$ p（i）= \ begin {案例} 1/2 ^ {n-1}，＆\ text {如果i= 0} \\ 1/2 ^ i，＆\ text {否则} \结束{案例} $$

假设使用线性搜索，并且每个搜索都成功 - 我们寻找的每个元素都存在。

是什么是检查随机搜索的搜索的平均节点数量（链接列表中的元素以随机顺序存储）组织，如果根据其降低的概率排序，则哪个节点的平均数量（即，它开始使用元素'1'，后跟元素'2'，然后'3'等，使用最后一个节点包含元素'0'。）对于n？

的大值

我知道第一部分的答案肯定不是 $ n / 2 $ （因为所有元素都不相同）但我这样做并不是那么多了......但是当排序时，我怀疑它应该是靠近 $$ \ sum_ {i= 1} ^ {n-1} i * { 1/2 ^ {i}} + n * 1/2 ^ {n-1} $$ ，因为它需要一个比较来获得第一个元素，两个到第二个等等，最后一个需要n比较时间0的概率0.我也找到了 $$ \ sum_ {i= o} ^ {} a * b ^ a= b /（1-b）^ 2 $ $ 在这种情况下，在这种情况下将等于2（b= 1/2），但我没有clue如何解决边缘案例 - '0'。 :(

我也知道这个线程但是每个数字都有相同的概率，它不完全相同。

我希望找到一个答案，因为它一直在困扰我，而且我对结果真的很好奇。
任何提示都将非常感谢！

Answer 1

嗯，让我们看看。如果我不正确地理解问题模型，请指出。

假设我们有 $ n= 5 $ 元素。假设它在 $ s= [1,3,4,0,2] $ 的方式中排序。然后使用线性搜索我们将使用概率 $（1/2）^ $ 在我们的搜索中有2个步骤，概率 $（1/2）^ 4 $ 在我们的搜索中有4个步骤。

So，找到一个元素的分段的平均步数是什么，给出任意排序 $ s $ ？假设 $ x $ - 我们搜索所需的步数。获取 $ x= i $ 步骤相当于请求搜索元素 $ k \ in \ {0， 1,2，..，n-1 \} $ 给出我们在 $ i $ th位置。这是 $$ p（x= i）=sum_ {k= 0} ^ {n-1} p（search \ for \ k \ | \ the \ component \ k \是\ \ \ \ position）p（\ component \ k \是\ \ \ \ position）$$ 然后我们注意到 $ p（\元素\ k \是\ \ \ \ position）=frac {（n-1）！} {n！}=frac {1} {n} $ 因为我们有一个固定位置的元素 $（n-1）！$ 其他元素的可能置入总计 $ n！$ 可能我们 $ n $ 元素的排列。 然后我们注意到 $ \ sum_ {k= 0} ^ {n-1} p（search \ for \ k \ | \ the \ compent \ k \ \ \ \ \位置）= 1 $ 。这意味着 $ p（x= i）=frac {1} {n} $ 。因此，期望只是 $ \ sum_ {k= 1} ^ {n} \ frac {k} {n}=frac {n + 1} {2} $ 。

当然，第二部分更容易得出，它只是 $$ e（x |排序\ in \ decsiveing \概率）=sum_ {k= 1} ^ {n-1} \ frac {k} {2 ^ {k}} + \ frac {n} $$ （只是注意到元素将来自< Span Class=“math-container”> $ 1 $ 到 $ n-1 $ ，然后元素 $ 0 $ ，但是 $ 0 $ 可能是预上元素，因为它具有与 $ n-1具有相同的概率$ ）。因此，我们只是计算概率分布的期望，虽然这次不适用于联合概率但有条件。