Нижняя граница нахождения медианы

Question

Предположим, нам дан список n чисел, и мы хотим найти число, которое больше или равно медианной. Я хочу узнать нижнюю границу для наихудшей сложности этой проблемы. Я знаю, что нижняя граница нахождения медианы равна 3 (n-1)/2. Но будет ли это одинаково, если мы хотим найти номер больше или равно медиана.

Answer 1

Я думаю, что самый большой элемент первой половины списка (+1) будет иметь эту функцию. Если вы проверите элемент n/2 + 1, и вы сохраните наибольшее значение, может быть не более n/2-1 элемент больше вашего медиана кандидата. Таким образом, выбранное число будет в верхней половине чисел, что означает: оно больше или равно медианной.

Таким образом, вы можете найти его в n/2+1.

Понадобится:

худший случай: п/2 comparsions и п/2 + 1 задания.

лучший случай: n/2 комплектов и 1 назначение.

Edit: Ответ на Ваш комментарий:

Да. Если n - четное число, любой случайный элемент будет больше или равен медиане с вероятностью не менее 0.5. Почему «не менее 0,5»? Там могут быть тестовые случаи, где почти все числа равны средней. В этих случаях вероятность будет выше. Если вы хотите знать правильную вероятность, вы должны проверить все элементы. В других тестовых случаях с разными номерами любой случайный элемент находился бы в верхней половине упорядоченного списка с вероятностью 0,5.

Если n нечетно, случайное число будет иметь эту функцию с вероятностью> 0,5. Это beacause n/2-0.5 элементов меньше, чем медианный, и n/2+0.5 элементов> = медиана (в общем случае). Если вы хотите, чтобы 0,5 была минимальной вероятностью, вы должны сделать некоторые изменения. У меня есть идея без каких-либо доказательств, может быть, кто-то соберет меня, если это не сработает: выберите 2 случайных значения из списка. Чем меньше будет действительное решение с вероятностью не менее 0,5.