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>, если сравнения не произошло.
Применим к обоим частям равенства операцию вычисления матожидания и воспользовавшись ее линейностью получим
