635
правок
Изменения
→Среднее время работы
<tex> =\dfrac {1}{j-i+1} + \dfrac {1}{j-i+1} = \dfrac {2}{j-i+1} </tex>
<tex> E[X] = \sum\limits_{i=1}^{n-1}\sum\limits_{j=i+1}^{n} \dfrac {2}{j-i+1} = \sum\limits_{i=1}^{n-1}\sum\limits_{k=1}^{n-i} \dfrac 2{k+1} < \sum\limits_{i=1}^{n-1}\sum\limits_{k=1}^{n-i} \dfrac 2{k} </tex> <tex>= \sum\limits_{i=1}^{n-1}O(\log n) = </tex><tex> = O(n \log n) </tex>
}}
Mатожидание времени работы быстрой сортировки будет <tex>O(n \log n)</tex>.
