Медиана медиан не является настоящей медианой. Правильный?

Question

Лично я считаю, что медиана медиан не является настоящей медианой. Правильный?
Так что, если приведенное выше утверждение верно, то почему использование медианы медиан в качестве опоры для разделения массива, чтобы найти временную сложность в КТИ МИН Эля в худшем случае O(п)? "N" - это число элементов.

Answer 1

Медиана медиан действительно только приблизительная, но не обязательно фактическая медиана.

Он используется в качестве оптимизации, чтобы вычислить опору для разбиения массива в алгоритмах, таких как Quicksort или Quickselect, так что сложность наихудшего случая O(n^2) избегается

Статья в Википедии об этом гласит:

Хотя этот подход довольно хорошо оптимизируется, на практике он обычно выигрывает, вместо этого выбирая случайные сводки, которые имеют среднее линейное время для выбора и среднее линейное время для сортировки и избегают затрат на вычисление сводки.