Режим поиска мультимножества в заданном временном интервале (наибольшая кратность)
Данная проблема:
Мультимножество - это множество, в котором некоторые элементы встречаются более одного раза (например, {a, f, b, b, e, c, b, g, a, i, b} является мультимножеством). Элементы взяты из полностью упорядоченного множества. Представление алгоритма, когда он представлен мультимножеством в качестве входных данных, находит элемент, который имеет наибольшее количество вхождений в мультимножестве (например, в {a, f, b, b, e, c, b, g, a, c, b}, б имеет большинство случаев). Алгоритм должен выполняться за время O(n lg n/M +n), где n - количество элементов в мультимножестве, а M - наибольшее число вхождений элемента в мультимножестве. Обратите внимание, что вы не знаете значение М.
[Подсказка: используйте стратегию "разделяй и властвуй", основанную на медиане списка. Подзадачи, генерируемые стратегией "разделяй и властвуй", не могут быть меньше "определенного" размера для достижения заданного временного ограничения.]
Наше первоначальное решение:
Наша идея состояла в том, чтобы использовать алгоритм большинства Мура, чтобы определить, содержал ли мультимножество кандидат в большинство (например, {a, b, b} имеет большинство, b). После определения, было ли это истиной или ложью, мы либо выводим результат, либо находим медиану списка, используя данный алгоритм (известный как Select), и разделяем список на три подсписка (элементы, меньшие и равные медиане, и элементы больше, чем медиана). Опять же, мы проверим каждый из списков, чтобы определить, присутствовал ли элемент контрольного числа, и если да, то это ваш результат.
Например, учитывая мультимножество {a, b, c, d, d, e, f}
Шаг 1: проверка на большинство. Ничего не найдено, разделите список на основе медианы.
Шаг 2: L1 = {a, b, c, d, d}, L2 = {e, f} Найдите большинство каждого. Ничего не найдено, снова разделите списки.
Шаг 3: L11 = {a, b, c} L12 = {d, d} L21 = {e} L22 = {f} Проверьте каждый на наличие большинства элементов. L12 возвращает d. В этом случае, d - это наиболее часто встречающиеся элементы в оригинальном мультимножестве, поэтому и есть ответ.
Проблемы, с которыми мы сталкиваемся, состоят в том, является ли этот тип алгоритма достаточно быстрым, а также может ли это быть сделано рекурсивно или требуется ли цикл, который завершается. Как подсказывает подсказка, подзадачи не могут быть меньше "определенного" размера, который мы считаем M (большинство случаев).
2 ответа
Если вы используете рекурсию самым простым способом, как описано в вашем посте, она не будет иметь желаемой сложности по времени. Зачем? Предположим, что ответный элемент самый большой. Тогда он всегда находится в правой ветви рекурсии. Но сначала мы вызываем левую ветвь, которая может пойти гораздо глубже, если все элементы различны (получая куски размера 1пока мы не хотим, чтобы они были меньше, чем M).
Вот правильное решение:
Давайте всегда разбивать массив на три части на каждом шаге, как описано в вашем вопросе. Теперь давайте отойдем в сторону и посмотрим, что у нас есть: рекурсивные вызовы образуют дерево. Чтобы получить желаемую сложность по времени, мы никогда не должны идти глубже, чем уровень, на котором находится ответ. Чтобы достичь этого, мы можем пройти по дереву, используя поиск в ширину с очередью вместо поиска в глубину. Вот и все.
Если вы хотите сделать это в реальной жизни, стоит рассмотреть возможность использования хеш-таблицы для отслеживания количества. Это может иметь амортизированную сложность O(1) на доступ к хеш-таблице, поэтому общая сложность следующего кода Python равна O(n).
import collections
C = collections.Counter(['a','f','b','b','e','c','b','g','a','i','b'])
most_common_element, highest_count = C.most_common(1)[0]