как найти медиану 5 отсортированного списка в O (logn) времени?

Question

Вот вопрос:

Есть 5 отсортированных списков A, B, C, D, E, которые имеют одинаковую длину n.Вопрос состоит в том, чтобы найти алгоритм, который может медианить этого 5 списка за O (logn) время.Я думаю об общей идее, но не могу понять, какую именно сложность она требует.

Предположим, медиана A, B, C, D, E - это a, b, c, d, e.И у нас есть a<b<c<d<e.Очевидно, что я мог бы выбросить первую половину массива A и последнюю половину массива E. Теперь у меня есть 5 новых массивов: B, C, D остаются прежними, у каждого есть n чисел;A и E имеют n / 2 числа слева.Затем я вычисляю медиану A и E как a и e, сравнивая их с b, c, d.Если новый порядок 5 медиан равен a'<b<e'<c<d, то я пропускаю первую половину a '(n / 4 числа) и последние n / 4 числа массива D, потому что нам нужно отбросить равные числа с обеих сторонокончательной медианы.Процесс продолжается ...

У меня такое ощущение, что алгоритм O (logn).Но я не знаю точного доказательства.На первых шагах входа в систему мы, безусловно, можем уменьшить число кандидатов до 3n, суммируя все оставшиеся номера из 5 списков.В первый раз мы выбрасываем n чисел, во второй раз как минимум n / 2 числа, в третий раз n / 4 числа и так далее.Тем не менее, я не знаю, как анализировать после того, как я получу 3n оставшихся чисел.

Может ли этот алгоритм действительно дать мне O (logn)?

Answer 1

Да, это действительно возможно.Просто посмотрите на эти утверждения

• Мы можем получить окончательный результат, только если у нас есть один список.Если у нас нет хотя бы двух списков, мы не можем об этом говорить.
• Каждый шаг алгоритма мы сокращаем наполовину двумя списками.Если в списке только один элемент, мы удаляем весь список.
• Давайте посчитаем, сколько шагов потребуется для удаления списка.При первом удалении мы будем удалять n / 2 элементов, второй - n / 4 и так далее до тех пор, пока не останется один элемент, когда мы наконец удалим список.Это займет около log (n) операций (не знаю, действительно ли это log (n) или log (n) +1, но в обоих случаях это O (log (n))).
• , нам нужно исключить 5 списков (операцию нахождения медианы в последнем списке можно обобщить на операцию сокращения списков).Для удаления одного из них требуется O (log (n)), поэтому мы сделаем все также и в O (log (n)), причина 5 постоянна.