此间大牛多，请教算法高手一个问题

雷达

8 V$ n! i) T! E
其实是个概率问题。
/ D9 N/ Y9 `* R! Q2 T; Y5 |1 _那本CLRS算法导论中，第 5-2 练习题。
! t; w7 M1 N1 p& e在 n 长的数列中有 k 个相同的 x 值，用顺序算法搜第一个 x 。
4 l& [, H$ ~) h# s' B1 [6 v问题就是这个人的表述
& B) f6 O; ~+ u" N' p7 [/ L+ ^8 I; Uhttps://math.stackexchange.com/q ... orithm-running-time
$ h, r# f- d% |+ E
$ ^; F2 C; I; m( a3 H+ U0 k按照答案，从头开始，之前没有出现过 x 的前提下，每一个元素是  x 的概率是 1/k; 不是  x 的概率是 1/(k+1)
7 M* r# I- U' ?1 ^' [2 J
+ H& g' {- i- i; J" h+ d% m" 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".

没看懂，这个   P(Xi)=1/(k+1) 怎么来的？ 按直觉，这个概率应该和 n 有关，假设 n = 10000, k = 5 的情况 和 n = 10, k = 5 的情况比较，概率应该不一样才对吧。

' I, q: {8 E' J老了，脑子水掉了，希望有高手解释清楚一点。多谢。

数值分析

& l: n2 I- X. n1 P
7 Q% \1 V+ F6 S6 n0 ]- u您对答案的理解似乎有误。
9 a  j0 z$ n+ j/ L. ^* w) x随机变量X是测试过的元素的数目
而随机变量Xi是另一组随机变量，每一个都是个indicator，取值是0或者1，含义为第i个元素是否被测试过，而不是该元素是否等于欲查找的值。
! K3 H! o8 u0 `1 |% n所以才有E(x)=sum(E(Xi))。
/ K. f; H, `3 ?/ t. d2 U$ e而如果 A[ i ]!= x，那么k个x值元素将整个数组分为了k+1个区间，而我们检查了这个元素，所以这个元素必须位于第一个区间，所以概率是1/(k+1)
: w/ c% R( a( C9 R; T您再想想？

老福

这个题目可以用递归的方法解决：

4 w8 h7 I" ~! H- s$ OE(k|n)=1*(k/n)+(1+E(k|n-1))*((n-k)/n)=1+((n-k)/n)*E(k|n-1)

* G2 M' Y" N3 b* p4 Z% N8 V$ p5 m$ W然后从头开始：
E(k|k)=1
E(k|k+1)=1+((1)/(k+1))*E(k|k)=1+(1/(k+1))=(k+2)/(k+1)
E(k|k+2)=1+(2/(k+2))*E(k|k+1)=1+(2/(k+2))*(k+2)/(k+1)=(k+3)/(k+1)
7 f. L+ l2 U* L' {3 w' ?6 [! KFinally, we can easily get E(k|n)=(n+1)/(k+1)
% j( O' W4 }  b, M3 K0 A- C0 L- y
  {, x9 \8 q8 W6 ~$ W2 m原文的解法有点绕，还没想明白。

雷达

数值分析 发表于 2022-3-26 10:32
( e5 Q$ n- ]0 E( w3 d' E您对答案的理解似乎有误。
/ P0 c; N& b9 Z4 B" [随机变量X是测试过的元素的数目
2 ?" M. i: D# V  Q8 J. W7 T) L而随机变量Xi是另一组随机变量，每一个都是个ind ...

" a# b* y9 {$ X明白了。
2 _# _/ Q6 {; T- Q4 a% E+ l是指的某非x元素在所有x之前的概率，实际上有 k+1 种可能的位置关系，所以在所有x之前就是 1/(k+1)
3 M: ?3 u) d# H1 Q9 l. X: m多谢

雷达

老福 发表于 2022-3-26 10:44
4 E# z2 Z7 G6 |6 f# X. X这个题目可以用递归的方法解决：
, c. C7 l" N! O2 j# D
E(k|n)=1*(k/n)+(1+E(k|n-1))*((n-k)/n)=1+((n-k)/n)*E(k|n-1)

. ?/ @$ u* b9 L7 `8 I
! q0 d' E- {9 }- Y+ L6 M6 V7 U递归法也是可以的。

老福

雷达 发表于 2022-3-26 11:07
/ o; p; T2 u( g5 Q' Z: k8 ?递归法也是可以的。

其实原文的解释似是而非，试想i=1的情形，对于概率P(X1=1), 无论A1是不是x, 这个概率应该是1, 而不是1/（k+1）。

数值分析

3 F1 Q: z" I# b( k* G- L

老福 发表于 2022-3-26 12:01
其实原文的解释似是而非，试想i=1的情形，对于概率P(X1=1), 无论A1是不是x, 这个概率应该是1, 而不是1/（ ...

( z  p4 p$ W( B
0 u- L7 V) c: k/ L0 R" B我觉得这个答案的作者其实是吧下标i作为元素的编号，而不是位置。
2 t. E3 b8 C/ K* U否则没法按元素是否等于x来分类，因为某一个位置是否等于x本身就是个随机事件。
; O5 {& d! c& V
而这个答案的作者其实是把每一个元素编了号，然后再考虑这个元素在数组中的位置的。故此对应于某一个元素，其是否等于x是个确定的事件，所以元素可以分为两类讨论，等于x的和不等于x的。
所以A[ i ]这个写法有点误导，这里这个A并不是要做搜索的那个数组，而是所有元素的列表。

老福

一开始我一直顺着原文的叙述试图理解概率为何为1/(k+1), 很困惑。谢谢数值分析坛友的提醒，终于想明白了。下面试着用同一思路但不同的语言叙述一下，作为总结。
8 @3 J; J# v: S1 I: e; S) n' U
  H, K5 }! S3 _6 @/ U. 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}.

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.
- u& C: Z- \8 }
For 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).

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).
+ v2 ^1 w4 z2 a+ B% l! b7 ~
4 H/ J* a; F7 t8 Q0 L/ e8 f! A- q6 ~! ^: T理解上述解法的一个关键点是对于所有不等于x的element，它能不能有机会被查验取决于而且只取决于它与k个值为x的elements的相对位置。