76
правок
Изменения
→Среднее время работы
Поскольку каждая пара элементов срановается не более одного раза, полное количество сравнений выражается как
<tex>X = \sum\limits_{i=1}^{n-1}\sum\limits_{j=i+1}^{n} X_{ij}</tex>, где <tex>X_{ij} = 1</tex>если произошло сравнение <tex>z_i</tex> и <tex>z_j</tex> и <tex>X_{ij} = 0</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>Pr\{z_i</tex> сравнивается с <tex>z_j\}</tex>- вероятность того, что <tex>z_i</tex> сравнивается с <tex>z_j</tex>. Поскольку предполагается, что все элементы в массиве различны, то при выборе <tex>x</tex> в качестве опорного элемента впоследствии не будут сравниваться никакие <tex>z_i</tex> и <tex>z_j</tex> для которых <tex>z_i < x < z_j</tex>. С другой стороны, если <tex>z_i</tex> выбран в качестве опорного, то он будет сравниваться с каждым элементом <tex>Z_{ij}</tex> кроме себя самого. Таким образом элементы <tex>z_i</tex> и <tex>z_j</tex> сравниваются тогда и только тогда когда первым в множестве <tex>Z_{ij}</tex> опорным элементом был выбран один из них.
<tex>Pr\{z_i</tex> сравнивается с <tex>z_j\} =
