152
правки
Изменения
Нет описания правки
== Анализ времени работы алгоритма ==
Пусть <tex>T(n)</tex> - время работы алгоритма для <tex>n</tex> элементов, тогда оно меньше, чем сумма:
# времени работы на сортировку групп и разбиение разбиения по рассекающему элементу, то есть <tex>Cn</tex>;
# времени работы для поиска медианы медиан, то есть <tex>T(\frac{n}{5})</tex>
# времени работы для поиска <tex>k</tex>-го элемента в одной из двух частей массива, то есть <tex>T(s)</tex>, где <tex>s</tex>- количество элементов в этой части. Но <tex>s</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> s \le \frac{7n}{10}</tex>, то есть в худшем случае <tex> s = \frac{7n}{10}</tex>.
Тогда получаем, что
Докажем по индукции:
# Очевидно, что для малых <tex> n </tex> выполняется неравенство <tex>T(n) \le 10Cn </tex>
# Тогда , по предположению индукции, <tex>T(\frac{n}{5}) \le 10C(\frac{n}{5}) = 2Cn</tex> и <tex> T(\frac{10n7n}{710}) \le 10C(\frac{7n}{10}) = 7Cn</tex>, тогда
<tex>T(n) \le T(\frac{n}{5}) + T(\frac{7n}{10}) + Cn = 2Cn + 7Cn + Cn = 10Cn \Rightarrow T(n) \le 10Cn</tex>
