预期的反演次数-从Cormen的引言到算法

预期的反演次数-从Cormen的引言到算法

我认为是正确的，但是我认为证明它的正确方法是使用条件期望：

对于所有X和Y，我们都有：E [X] = E [E [X | Y]]

那么在你的情况下：

E（i + 1）= E [x（i + 1）] = E [E [x（i + 1）| x（i）]] = E [SUM（k）/（1 + i）+ x（i）] = i
/ 2 + E [x（i）] = i / 2 + E（i）

关于第二个陈述：

如果：

E（n）= n *（n-1）/ 4。

那么E（n + 1）=（n + 1） n / 4 =（n-1） n / 4 + 2 * n / 4 =（n-1）* n / 4 + n / 2 = E（
n）+ n / 2

所以n *（n-1）/ 4。验证所有n> = 2的递归关系，并验证n = 2的递归关系

所以E（n）= n *（n-1）/ 4

希望我了解您的问题，对您有帮助