Изменения

Перейти к: навигация, поиск

Поиск k-ой порядковой статистики за линейное время

Нет изменений в размере, 23:30, 7 июня 2011
м
Анализ времени работы алгоритма
== Анализ времени работы алгоритма ==
Пусть <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>.
152
правки

Навигация