0

认为指标随机变量 X k和值T(max(k - 1, n - k))是独立的。

答案是

当我们知道 k-1 和 nk 的最大值时,X_k 等于 1 的概率不变。换句话说,Pr{X_k =a| max(k-1, nk)=m} = Pr{X_k=a} for a=0,1 and m=k-1, nk 所以 X_k 和 max(k-1, nk) 是独立的。

现在,根据我的理解,k-1 是子数组的下侧,其中数组 < k 的每个元素和 nk 是数组的上侧,其中数组的每个元素 > k。所以我们可以将 k 视为支点。X_k 是指示随机变量,当子数组 A[p..q] 恰好有 k 个元素时,X_k = 1。[参考 Cormen 的算法介绍第 9 章。第 9.2 节:预期线性时间的选择]。

现在,当我们知道 k-1 和 nk 的最大值时,答案是 X_k=1。我相信 k-1 的最大值将是数组的第 k-1 个元素,而 nk 的最大值是数组的第 n 个元素。最大元素与指标随机变量 1 的关系是什么?

Pr{X_k=a} 给定 max(k-1, nk)

max(k-1, nk) 表示最大元素应该在第 n 个位置。

另外,我不清楚am的定义。

我在 CLRS 解决方案链接问题 9.2-2 的答案中找到了这个问题。

虽然答案是在链接中定义的,但我相信对这个答案的更多解释会更有帮助。

4

0 回答 0