689
правок
Изменения
м
Новая страница: «<tex>X = \sum\limits_{i=1}^{n-1}\sum\limits_{j=i+1}^{n} X_{ij}</tex> <tex>E[X] = E\left[\sum\limits_{i=1}^{n-1}\sum\limits_{j=i+1}^{n} X_{ij}\right] = \sum\limits_{…»
<tex>X = \sum\limits_{i=1}^{n-1}\sum\limits_{j=i+1}^{n} X_{ij}</tex>
<tex>E[X] = E\left[\sum\limits_{i=1}^{n-1}\sum\limits_{j=i+1}^{n} X_{ij}\right] = \sum\limits_{i=1}^{n-1}\sum\limits_{j=i+1}^{n} E[X_{ij}] = \sum\limits_{i=1}^{n-1}\sum\limits_{j=i+1}^{n} Pr\{z_i</tex> сравнивается с <tex>z_j\}</tex>
<tex> E[X] = \sum\limits_{i=1}^{n-1}\sum\limits_{j=i+1}^{n} \frac {2}{j-i+1} = \sum\limits_{i=1}^{n-1}\sum\limits_{k=1}^{n-i} \frac 2{k+1} < \sum\limits_{i=1}^{n-1}\sum\limits_{k=1}^{n-i} \frac 2{k} = \sum\limits_{i=1}^{n-1}O(\log n) = O(n \log n)</tex>
<tex>E[X] = E\left[\sum\limits_{i=1}^{n-1}\sum\limits_{j=i+1}^{n} X_{ij}\right] = \sum\limits_{i=1}^{n-1}\sum\limits_{j=i+1}^{n} E[X_{ij}] = \sum\limits_{i=1}^{n-1}\sum\limits_{j=i+1}^{n} Pr\{z_i</tex> сравнивается с <tex>z_j\}</tex>
<tex> E[X] = \sum\limits_{i=1}^{n-1}\sum\limits_{j=i+1}^{n} \frac {2}{j-i+1} = \sum\limits_{i=1}^{n-1}\sum\limits_{k=1}^{n-i} \frac 2{k+1} < \sum\limits_{i=1}^{n-1}\sum\limits_{k=1}^{n-i} \frac 2{k} = \sum\limits_{i=1}^{n-1}O(\log n) = O(n \log n)</tex>
