55
правок
Изменения
Нет описания правки
== Анализ времени работы алгоритма ==
Чтобы проанализировать время работы алгоритма, сначала определим нижнюю границу для количества элементов, превышающих по величине рассекающий элемент <tex>x</tex>. В общем случае как минимум половина медиан, найденных на втором шаге, больше или равны медианы медиан <tex>x</tex>. Таким образом, как минимум <tex>n</tex> <tex>/</tex> <tex>10</tex> содержат по <tex>3</tex> превышающих величину <tex>x</tex>, за исключение группы, в которой меньше <tex>5</tex> элементов и ещё одной группы, содержащей сам элемент <tex>x</tex>. Таким образом получаем, что количество элементов меньших элемента <tex>x</tex>, не менее <tex>\frac{3n}{10}</tex>, где <tex>n</tex> это количество элементов в массиве.
Проведя аналогичные рассуждения для элементов, которые меньше по величине, чем рассекающий элемент <tex>x</tex>, мы получим, что как минимум <tex>\frac{3n}{10}</tex> меньше, чем элемент <tex>x</tex>. Теперь проведем анализ времени работы алгоритма.
Пусть <tex>T(n)</tex> — время работы алгоритма для <tex>n</tex> элементов, тогда оно не больше, чем сумма:
# времени работы на сортировку групп и разбиение по рассекающему элементу, то есть <tex>Cn</tex>;
