Bubble Sort (UVa 12004 World Finals Warmup 2011 2)

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=242&page=show_problem&problem=3155

問題

長さnの順列でバブルソートをした時の交換回数の期待値を求めよ。
1<=n<=500,000

解法

数値のペアに着目すると2つの値は正順になっているか逆順になっているかの2通りしか無いので期待値は1/2になる。なので、期待値の線形性より答えはn*(n-1)/4になる。