635
правок
Изменения
→Среднее время работы
|statement=Время работы алгоритма быстрой сортировки равно <tex>O(n \log n)</tex>.
|proof=Пусть Х {{---}} полное количество сравнений элементов с опорным за время работы сортировки. Нам необходимо вычислить полное количество сравнений.
Переименуем элементы массива как <tex>z_1...\ldots z_n</tex>, где <tex>z_i</tex> наименьший по порядку элемент.Также введем множество <tex>Z_{ij} = \{z_i, z_{i+1}...\ldots z_j\}</tex>.
Заметим, что сравнение каждой пары элементов происходит не больше одного раза, так как элемент сравнивается с опорным, а опорный элемент после разбиения больше не будет участвовать в сравнении.
