算法导论(第三版)习题9.2-2

9.2-2 请讨论：指示器随机变量$X_{k}$和 $T(max(k-1, n-k))$是独立的。

来自知乎我的回答

这个问题其实挺简单的，注意下面几点就可以了

• $T(n)$：算法 Randomized-select 在含有 n 个元素的输入数组 $A[p..r]$上的运行时间， 是一个随机变量
• $T(n)$单调递增

到这里应该就可以结束了， 但稍微深入一点，

• $X_{k}$:子数组 $A[p..q]$正好包含k个元素的概率。
• $T(max(k-1, n-k))$: 算法 Randomized-select 在含有 $max(k - 1, n -k)$个元素数组上的运行时间

如果还没理解 $X_{k}$和 $T(max(k-1, n-k))$独立的话，继续往下看。

举个栗子吧( 注意 $T(n)$的定义 )：

• 子数组 $A[p..q]$正好有4个元素跟 $T(3)$有关系吗？
• 进而子数组 $A[p..q]$正好有4个元素跟 $T(4)$有关系吗？
• 更进一步子数组 $A[p..q]$正好有k个元素跟 $T(k)$有关系吗(这里仅仅只是使用了相同的数字k, 你能说我掷骰子第一次掷中3 跟 第二次掷中3是相关的吗)?
• 最后一步子数组 $A[p..q]$正好有k个元素跟 $T(max(k-1, n-k)$有关系吗? (这不就是$X_{k}$和 $T(max(k-1, n-k))$独立吗？)

哎 ，如果还看不懂的话，我也没什么可说的了。找本概率论多看看，培养培养感觉，主要概率这中西太抽象，多培养培养感觉就好。