Вычисление медианы по алгоритму черного ящика за время O (n)

Question

проблема заключается в следующем:

для массива A размера n и алгоритма B и B (A, n) = b, где b такой элемент A, что | {1 <= i <= n | a_i> Ь} |> = п / 10
| {1 <= i <= n | a_i> Ь} | <= п / 10 </p>

Временная сложность B равна O (n).

мне нужно найти медиану в O (n).

Я попытался решить этот вопрос, применив B и затем найдя группы элементов, которые меньше, чем b, давайте назовем эту группу как C. и элементы больше, чем b, давайте назовем эту группу D. мы можем получить группы C и D, пройдя через массив A в O (n). теперь я могу применить алгоритм B к меньшей группе из вышеприведенного, потому что медиана отсутствует, и, применяя тот же принцип, в конце я могу получить медианный элемент. временная сложность O (nlogn)

Я не могу найти решение, которое работает на O (n).

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

Answer 1

Предполагается, что вы используете функцию B (), чтобы выбрать элемент поворота для алгоритма быстрого выбора: https://en.wikipedia.org/wiki/Quickselect

Похоже, вы уже думаете именно об этой процедуре, поэтому у вас уже есть алгоритм,и вы просто неправильно вычисляете сложность.

На каждой итерации вы запускаете процедуру с линейным временем для списка, который не превышает 9/10 от размера списка на предыдущей итерации, поэтому наихудший случайсложность

O (n + n * 0,9 + n * 0,9 ^ 2 + n * 0,9 ^ 3 ...)

Подобные геометрические прогрессии сходятся к постоянному множителю:

Пусть T = 1 + 0,9 ^ 1 + 0,9 ^ 2 + ...

Легко видеть, что

T - T * 0,9 = 1, поэтому

T * (0,1) = 1 и T = 10

Таким образом, общее количество элементов, обработанных во всех итерациях, составляет менее 10n, и поэтому ваш алгоритм занимает O (n) времени.