有人可以解释一下这个证明中的 X、I 和 Pr 是什么吗？还有为什么第一个 sigma 从 j=i+1 开始？
Can someone explain me what are X, I and Pr in this proof ? and also why first sigma start from j=i+1?
我正在阅读 CLRS 算法，我看到了这个定理。
定理 11.2: 在哈希 table 中，通过链接解决冲突，一个成功的搜索
需要 平均时间：theta(1+n/m) 在简单统一散列的假设下。
在这个定理中，m => table 中的槽数和 n => 每个槽中的元素数 。
这就是证明：
请帮帮我。我完全看不懂这个黄色部分:(
I就是Indicator function。满足条件时其值为1，否则为0。
X_ij是哈希冲突的指标。即，h(k_i) == h(k_j)时X_ij == 1，h(k_i) != h(k_j)时X_ij == 0。
Pr是概率。突出显示的语句表示哈希冲突的概率为 1/m.
总和从i+1开始，因为为了找到x_i，我们只需要检查在x_i之后插入的元素。插入之前 x_i的那些将在列表中位于之后，因此搜索将在到达它们之前终止。
我正在阅读 CLRS 算法，我看到了这个定理。
定理 11.2: 在哈希 table 中，通过链接解决冲突，一个成功的搜索
需要 平均时间：theta(1+n/m) 在简单统一散列的假设下。
在这个定理中，m => table 中的槽数和 n => 每个槽中的元素数 。
这就是证明：
请帮帮我。我完全看不懂这个黄色部分:(
I就是Indicator function。满足条件时其值为1，否则为0。
X_ij是哈希冲突的指标。即，h(k_i) == h(k_j)时X_ij == 1，h(k_i) != h(k_j)时X_ij == 0。
Pr是概率。突出显示的语句表示哈希冲突的概率为 1/m.
总和从i+1开始，因为为了找到x_i，我们只需要检查在x_i之后插入的元素。插入之前 x_i的那些将在列表中位于之后，因此搜索将在到达它们之前终止。