152
правки
Изменения
→Анализ времени работы алгоритма
== Анализ времени работы алгоритма ==
Пусть <tex>T(n)</tex> время работы алгоритма для <tex>n</tex> элементов, тогда она меньше, чем <tex>Cn</tex> - время работы, на сортировку групп, и разбиение по рассекающему элементу. Плюс время сумма время работы для поиска медианы медиан, то есть <tex>T(\frac{n}{5})</tex>. И кроме того время работы для поиска <tex>k</tex>-го элемента в одной из двух частей массива, то есть <tex>T(k)</tex>, где <tex>k</tex>, количество элементов в этой части, но <tex>k</tex> не превосходит <tex>\frac{7n}{10}</tex>, так как чисел меньше рассекающего элемента не менее <tex>\frac{3n}{10}</tex> - это <tex>\frac{n}{10}</tex> медиан меньшие медианы медиан плюс не менее <tex>\frac{2n}{10}</tex> элементов меньшие этих медиан, с другой стороны чисел больших рассекающего элемента так же менее <tex>\frac{3n}{10}</tex>, следовательно в худшем случае <tex> k = \frac{7n}{10}. Тогда получаем, что
<tex>T(n) \le T(\frac{n}{5}) + T(\frac{7n}{10}) + Cn </tex>
Тогда покажем, что для всех <tex> n </tex> выполняется неравенство <tex>T(n) \le 10Cn </tex>.
