c++ - 列表搜索的最佳/最坏情况下的步数

问题描述

我有一个长度为“n”的列表，它是一个未知的偶数。具有偶数索引的单元格中存在键“x”的概率是其他单元格的两倍。例如：

 _ _ _ _ _ _ _ _ _ _ _ _
|_0_|_1_|_2_|_3_|_4_|_5_|    index

  |   |   |   |   |   |
 _ _ _ _ _ _ _ _ _ _ _ _
|_9_|_5_|_7_|_3_|_8_|_0_|    value

因为“x”肯定存在，所以所有概率的总和为 1。因此每个单元格可以有 1/概率长度；但根据第一行，分布是不同的。因此：

p(T) = 1
p(0) + p(2) + p(4) = 2 * (p(1) + p(3) + p(5))

如何计算平均比较时间？

标签： c++algorithm

这是在您的搜索x索引中找到的概率：i

$\begin{align*} Po =& \text{probability of an element on odd index to contain } x\\ Pe =& \text{probability of an element on even index to contain } x\\ Pe =& 2Po \end{align*} \\ \text{Let's find } Po \\ \begin{align*} \frac{n}{2}Po + \frac{n}{2}Pe =& 1 \\ \frac{n}{2}Po + \frac{n}{2}2Po =& 1 \\ \frac{3n}{2}Po =& 1 \\ Po =& \frac{2}{3n} \\ Pe =& \frac{4}{3n} \end{align*} \\ \text{Now let's find the probability to find } x \text{ at element } i \text{ in our search:} \\ Pi = \begin{cases} ~ \frac{i}{2} \cdot (Po + Pe) + Pe = \frac{i}{2} \cdot \frac{2}{n} + \frac{4}{3n} = \frac{i+\frac{4}{3}}{n} & \text{ if } i \text{ is even} \\ ~ \frac{i+1}{2} \cdot (Po + Pe) = \frac{i+1}{2} \cdot \frac{2}{n} = \frac{i+1}{n} & \text{ if } i \text{ is odd} \\ \end{cases}$

c++ - 列表搜索的最佳/最坏情况下的步数

问题描述

解决方案

推荐阅读