当搜索元素的可能性不同时如何找到平均成功搜索（线性和 BST）
How to find average successful search when elements are NOT equally likely to be searched (linear and BST)
我正在学习搜索，我想知道当搜索每个元素的可能性不同时，线性和 BST 的平均成功搜索。但是，在这种情况下，我并没有找到该怎么做:(
例如，我有一个包含 3 个元素 (5, 4, 8) 的列表，每个元素被搜索的概率分别为 (0.1, 0.05, 0.05)。如果执行线性搜索或 BST，一次成功搜索检查的平均元素数是多少？
设置是元素 i 有一个值 v[i]，一个概率 p[i]，搜索该元素将进行 c[i] 比较。
在你的例子中我们给出了
v = [5, 4, 8]
p = [0.1, 0.05, 0.05]
如果您尝试线性搜索，比较次数将为
c = [1, 2, 3]
您要做的是根据执行此操作的可能性对每个计数进行加权，然后除以成功搜索的总体可能性。即：
print(sum([p[i] * c[i] for i in range(len(c))]) / sum(p))
在你的情况下，结果是 1.75。
如果您要切换到二进制搜索，计数将变为 c = [1, 2, 2]，而计算结果变为 1.5。 （这是有道理的，你甚至有机会摘根或摘叶。）
如果您想包括不成功搜索的可能性，那么您只需添加不成功搜索的次数和概率。所以对于线性你可能会得到：
p = [0.1, 0.05, 0.05, 0.8]
c = [1, 2, 3, 3]
现在你的答案是 2.75。那是因为您大部分时间都在进行不成功的搜索，这需要 3.
对于不平衡的二分搜索，它变得更加复杂，因为您必须以概率包含每个缺失的范围。但是原理还是一样的。
我正在学习搜索，我想知道当搜索每个元素的可能性不同时，线性和 BST 的平均成功搜索。但是，在这种情况下，我并没有找到该怎么做:(
例如，我有一个包含 3 个元素 (5, 4, 8) 的列表，每个元素被搜索的概率分别为 (0.1, 0.05, 0.05)。如果执行线性搜索或 BST，一次成功搜索检查的平均元素数是多少？
设置是元素 i 有一个值 v[i]，一个概率 p[i]，搜索该元素将进行 c[i] 比较。
在你的例子中我们给出了
v = [5, 4, 8]
p = [0.1, 0.05, 0.05]
如果您尝试线性搜索，比较次数将为
c = [1, 2, 3]
您要做的是根据执行此操作的可能性对每个计数进行加权，然后除以成功搜索的总体可能性。即：
print(sum([p[i] * c[i] for i in range(len(c))]) / sum(p))
在你的情况下，结果是 1.75。
如果您要切换到二进制搜索，计数将变为 c = [1, 2, 2]，而计算结果变为 1.5。 （这是有道理的，你甚至有机会摘根或摘叶。）
如果您想包括不成功搜索的可能性，那么您只需添加不成功搜索的次数和概率。所以对于线性你可能会得到：
p = [0.1, 0.05, 0.05, 0.8]
c = [1, 2, 3, 3]
现在你的答案是 2.75。那是因为您大部分时间都在进行不成功的搜索，这需要 3.
对于不平衡的二分搜索，它变得更加复杂，因为您必须以概率包含每个缺失的范围。但是原理还是一样的。