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