爱吱声

标题: 此间大牛多，请教算法高手一个问题 [打印本页]
作者: 雷达    时间: 2022-3-26 08:43
标题: 此间大牛多，请教算法高手一个问题
本帖最后由 雷达 于 2022-3-26 08:54 编辑 7 _% o7 X3 D4 c, J
! e% l- b) B4 b0 I* t2 _9 q# D
其实是个概率问题。
/ V1 C$ y9 J" U/ s  ?# B6 Z那本CLRS算法导论中，第 5-2 练习题。* x% p$ j0 G+ [, a1 J
在 n 长的数列中有 k 个相同的 x 值，用顺序算法搜第一个 x 。
! e6 M* f" \# f问题就是这个人的表述% R6 A  j# \* G; n- }+ G
https://math.stackexchange.com/q ... orithm-running-time1 ]! h' Y& {* ~

1 [# P; f, z. @/ [按照答案，从头开始，之前没有出现过 x 的前提下，每一个元素是  x 的概率是 1/k; 不是  x 的概率是 1/(k+1)
3 e" M' \/ }5 p9 O# \% l5 i4 ^! |( R) D: F8 }2 l
" If i is an index such that A≠x then P(Xi)=1/(k+1) since we examine it only if it occurs before every one of the k indices that contains x".
9 R) w4 l# |4 |# c2 U, z0 \9 N: a* L4 c& x; r9 C
没看懂，这个   P(Xi)=1/(k+1) 怎么来的？ 按直觉，这个概率应该和 n 有关，假设 n = 10000, k = 5 的情况 和 n = 10, k = 5 的情况比较，概率应该不一样才对吧。) N: ]6 ?" C2 k$ q) W) Q' M, z1 S. N( x6 I
) F9 V0 R  l& M4 u1 ], |! n1 I
老了，脑子水掉了，希望有高手解释清楚一点。多谢。
作者: 数值分析    时间: 2022-3-26 10:32
本帖最后由 数值分析 于 2022-3-26 10:56 编辑 4 c  w8 b& v6 q7 z8 w9 U3 e
/ d, p9 f$ z# b4 O0 b- H1 d
您对答案的理解似乎有误。& W7 D* q* h  z# _9 Z7 ?/ T7 |7 ~
随机变量X是测试过的元素的数目- |  G3 r1 c+ `0 b
而随机变量Xi是另一组随机变量，每一个都是个indicator，取值是0或者1，含义为第i个元素是否被测试过，而不是该元素是否等于欲查找的值。$ |# r) i: ^  k3 ?" G
所以才有E(x)=sum(E(Xi))。
1 H# C, t% F( R& O而如果 A[ i ]!= x，那么k个x值元素将整个数组分为了k+1个区间，而我们检查了这个元素，所以这个元素必须位于第一个区间，所以概率是1/(k+1)1 ?. x/ m" q7 u# p4 T' Z- g4 e
您再想想？
作者: 老福    时间: 2022-3-26 10:44
这个题目可以用递归的方法解决：
* R& D- d5 z0 n. Z5 G! Y% m0 `) k
8 d0 e8 b. I- J& b3 W5 fE(k|n)=1*(k/n)+(1+E(k|n-1))*((n-k)/n)=1+((n-k)/n)*E(k|n-1)3 ~  W  C% Y! d/ q, O9 _9 X/ L$ d" E6 x

8 D0 z7 W+ \" p, c. X% _6 y: s* ?然后从头开始：, l: F3 F$ \) `. i' L) t
E(k|k)=16 v( w. `- ]0 l3 F' E& m
E(k|k+1)=1+((1)/(k+1))*E(k|k)=1+(1/(k+1))=(k+2)/(k+1)
( M" t" y% r5 r& wE(k|k+2)=1+(2/(k+2))*E(k|k+1)=1+(2/(k+2))*(k+2)/(k+1)=(k+3)/(k+1)
! z% z  O' a* |, L# w& Q" A; JFinally, we can easily get E(k|n)=(n+1)/(k+1)* ], p" F7 \* ~
! E: q$ c- E/ h9 x
原文的解法有点绕，还没想明白。
作者: 雷达    时间: 2022-3-26 11:00
数值分析 发表于 2022-3-26 10:32
5 m2 l5 S: c+ u. ^$ H" S; g( i您对答案的理解似乎有误。+ u6 b+ C( u" \/ x8 ?1 X0 G2 w" Y) B; a
随机变量X是测试过的元素的数目0 O; D/ ]* C9 d6 j( @0 \2 _
而随机变量Xi是另一组随机变量，每一个都是个ind ...
' ~/ c7 x" F* u7 O" V2 z" J, N$ F
明白了。8 H- N/ _1 [, w$ O% O9 U% O2 J5 F
是指的某非x元素在所有x之前的概率，实际上有 k+1 种可能的位置关系，所以在所有x之前就是 1/(k+1)3 ^6 r- t/ h7 d" l1 \; k, _
多谢
作者: 雷达    时间: 2022-3-26 11:07
老福 发表于 2022-3-26 10:44+ O/ m! G, o! s
这个题目可以用递归的方法解决：
4 e$ g7 U( W" |$ X# h1 A: f1 B& V7 Q
E(k|n)=1*(k/n)+(1+E(k|n-1))*((n-k)/n)=1+((n-k)/n)*E(k|n-1)
: J% ?  E+ W2 b% J

# K9 S- q4 x0 C% |: X递归法也是可以的。
作者: 老福    时间: 2022-3-26 12:01
雷达 发表于 2022-3-26 11:07: p" ^! ~; H+ s( z( u$ u
递归法也是可以的。
: S1 Z: f* J# A) X+ T
其实原文的解释似是而非，试想i=1的情形，对于概率P(X1=1), 无论A1是不是x, 这个概率应该是1, 而不是1/（k+1）。
作者: 数值分析    时间: 2022-3-26 14:46
本帖最后由 数值分析 于 2022-3-26 14:51 编辑 . f" N4 y! w5 ]
老福 发表于 2022-3-26 12:01
) {9 V( m9 Y/ o% ]其实原文的解释似是而非，试想i=1的情形，对于概率P(X1=1), 无论A1是不是x, 这个概率应该是1, 而不是1/（ ...

# W& C0 T" s) B/ A( S! w3 X9 w" e7 b; v/ K0 ~
我觉得这个答案的作者其实是吧下标i作为元素的编号，而不是位置。. k, m6 t8 _7 @+ l: A; ^4 E
否则没法按元素是否等于x来分类，因为某一个位置是否等于x本身就是个随机事件。
  U( X# `- F3 C. a! d( K. Q
1 Y$ K5 l: c/ m! X# A/ ^而这个答案的作者其实是把每一个元素编了号，然后再考虑这个元素在数组中的位置的。故此对应于某一个元素，其是否等于x是个确定的事件，所以元素可以分为两类讨论，等于x的和不等于x的。9 Z; g( X8 N2 d% ^+ {, E+ b
所以A[ i ]这个写法有点误导，这里这个A并不是要做搜索的那个数组，而是所有元素的列表。
作者: 老福    时间: 2022-3-27 00:32
一开始我一直顺着原文的叙述试图理解概率为何为1/(k+1), 很困惑。谢谢数值分析坛友的提醒，终于想明白了。下面试着用同一思路但不同的语言叙述一下，作为总结。- g: \3 q2 G( v6 q% N+ h

$ \- I) v# R" s: ILet S be the set of the n elements in which there are k and only k elements that have value x. For each element w, let I be the indicator if w is examined or not, that is, I(w) = 1 if w is examined and 0 if w is not examined. X, the number of elements being examined, will be the sum of I(w) for all w in S. Accordingly, E[X] will be the sum of E[I(w)]=P{I(w)=1}. " L1 s! N5 _2 O
! A  f6 z. X3 K5 X' h
For w that has a value x, the chance of w being examined is the chance that w is at the first position of a permutation of k x-valued elements. Therefore it's 1/k.
7 f, K! c+ ^: m( t  ]* y
) L+ Y& N7 g4 |+ J( h# a, |3 \8 jFor w that has a value not being x, the chance of x being examined is the chance that w is at the first position of a permutation of all k x-valued elements plus w. Therefore it's 1/(k+1).
4 ?& p  P; q; h4 c* L0 p. |: q3 Q; o! B, q% n
There are k elements that have value x and n-k elements that are not equal to x, so the sum of all these probabilities will be k*(1/k) + (n-k)*(1/(k+1)) = (n+1)/(k+1).
  j$ s/ _) p+ F+ H, B, ?# n) x2 [, J6 X2 m8 d
理解上述解法的一个关键点是对于所有不等于x的element，它能不能有机会被查验取决于而且只取决于它与k个值为x的elements的相对位置。



欢迎光临 爱吱声 (http://aswetalk.net/bbs/) Powered by Discuz! X3.2