顺序搜索在几何概率分布下的平均情况分析

Question

顺序搜索在几何概率分布下的平均情况分析

algorithmruntimetime-complexityanalysisasymptotic-complexity

3

我有点意识到如何在均匀分布中获取平均运行时间。比如说我们有6个数组元素。

| 1/6  | 1/6   | 1/6  | 1/6   | 1/6  |  1/6   |

以下是具有均匀概率分布的搜索元素在数组中出现在每个下标位置的数组。

因此，在均匀分布中获取平均运行时间将像以下解决方案一样：

T(n) = (1/6)*1 + (1/6)*2 + (1/6)*3 + (1/6)*4 + (1/6)*5 + (1/6)*6
     = (1/6) * ( 1 + 2 + 3 + 4 + 5 + 6 )
     =  3.5

或者在express中表示为n个项的情况下：

T(n) = (1/n) * ((n(n+1))/2)
     = (n+1) / 2
     = ϴ(n)

但是在几何概率分布下，顺序搜索的平均关键字比较次数如何呢？

示例：

Prob(target X is in the jth position) = 1/(2^(j+1))
where j = 0, 1, 2,3,4,5,6,...


| 1/(2^(0+1))  | 1/(2^(1+1))  | 1/(2^(2+1)) | 1/(2^(3+1))  | 1/(2^(4+1))  |  1/(2^(5+1))   |

那么

T(j) = ((1/2)* 1) + ((1/4)* 2) + ((1/8)* 3) + ((1/16)* 4) + ((1/32)* 5) + ((1/64)* 6)
     =  .5 + .25(2) + .125(3) + .0625(4) + .03125(5) + .015625(6)
     =  .5 + .5 + .375 + .25 + .15625 + .09375

     =  1.875

我不知道如何用j语言来表达它：

 T(j) = ?

什么是上界O(j)？下界Ω(j)？紧密边界ϴ(j)？

任何帮助或想法将不胜感激。

更新：

我认为获取运行时间的公式如下：

 T(j) = ((sum of geometric series) or (sum of geometric series / n)?)* (n((n+1))/2)

我需要的是当数列中每个元素的值为1/(2^(j+1))，其中j=0,1,2,...一直到n时，等比数列求和公式。请帮忙。

更新：

我已经想出等比数列求和公式为1-(1/2^n)。

 T(n) = (1-1/(2^n))/n * (n(n+1)/2)
      = (n+1)/2 - (n+1)/(2^(n+1))

现在，我的问题是什么是大O符号、大Ω符号、大θ符号、小o符号和小ω符号？有没有可能一个算法没有下界？

- alyssaeliyah

1

你想让 T(j) 计算什么？ - SteamyThePunk

我的意思是，如果j只是另一个用于索引数量的变量，那么就使用与您先前示例中相同的方法。 - SteamyThePunk

对于您的具体示例，如果您在6处截断，则没有有效的概率分布，因为它总和为63/64而不是1。您需要按64/63加权您的答案。一般来说，Sum（x * p（x））是离散分布下X的期望值的定义。 - pjs

你只需要交换代数等式即可。1/2 + 1/4 + 1/8 是当 j 从 0 到 3 时，1/(2^(j+1)) 的和... 这就是阿基里斯与乌龟的悖论，你可以很容易地发现你可以用 n 来重新表述它。P(n) = -1/(2^(n+1)) + 1现在只需替换等效项，就像之前的例子一样。 - SteamyThePunk

1

你能解释一下你是如何得出结果 (n+1)/2 - (n+1)/(2^(n+1)) 的吗？这个结果对我来说有些可疑，特别是你只是乘以了 n(n+1)/2。 - meowgoesthedog

显示剩余2条评论

2个回答