76
правок
Изменения
→Среднее время работы
Переименуем элементы массива как <tex>z_1...z_n</tex>, где <tex>z_i</tex> наименьший по порядку элемент.
Также введем множество <tex>Z_{ij} = \{z_i, z_{i+1}...z_j\}</tex>.
Заметим, что сравнеие каждой пары элементов происходит не больше одного раза, так как элемент сравнивается с опорным, а опорный элемент после разбиения больше не будет участвовать в сравнении.
Поскольку каждая пара элементов срановается не более одного раза, полное количество сравнений выражается как
