我有点意识到如何在均匀分布中获取平均运行时间。比如说我们有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符号和小ω符号? 有没有可能一个算法没有下界?
(n+1)/2 - (n+1)/(2^(n+1))
的吗?这个结果对我来说有些可疑,特别是你只是乘以了n(n+1)/2
。 - meowgoesthedog