Где я могу использовать технику из алгоритма большинства голосов - PullRequest
Новая
       28

Где я могу использовать технику из алгоритма большинства голосов

6 голосов
/ 24 мая 2011

Как видно из ответов на Алгоритм большинства линейного времени? , можно вычислить большинство элементов массива в линейном времени и log(n) пространстве.

Было показано, что каждый, кто видит этот алгоритм, считает, что это крутая техника. Но обобщает ли идея новые алгоритмы?

Кажется, скрытая сила этого алгоритма заключается в том, что он поддерживает счетчик, который играет сложную роль, такую ​​как "(количество элементов большинства до сих пор) - (количество вторых элементов пока)". Есть ли другие алгоритмы, основанные на той же идее?

Ответы [ 3 ]

6 голосов
/ 24 мая 2011

Хм, давайте сначала начнем понимать, почему алгоритм работает, чтобы "изолировать" идеи там.

Смысл алгоритма в том, что если у вас есть элемент контрольного пакета, то вы можете сопоставить каждый его элемент с «другим» элементом, и тогда у вас будет еще «лишний».

Итак, у нас просто есть счетчик, который подсчитывает количество «лишних» вхождений нашего гостевого ответа. Если он достигает 0, то он не является мажоритарным элементом для подпоследовательности, начиная с того момента, когда мы «выбрали» текущий «элемент» в качестве основного гостевого элемента на «текущую» позицию. Кроме того, поскольку наш «гостевой» элемент соответствует каждому вхождению другого элемента в рассматриваемой подпоследовательности, в рассматриваемой подпоследовательности отсутствуют основные элементы.

Теперь, так как:

  1. наш алгоритм дает правильный ответ, только если есть главный элемент, и
  2. если есть главный элемент, тогда все равно будет, если мы проигнорируем подпоследовательность "current", когда счетчик обнулится

очевидно, что в случае противоречия очевидно, что если существует главный элемент, то у нас есть суффикс всей последовательности, когда счетчик никогда не достигает нуля.

Теперь: в чем заключается идея, которую можно использовать в новых алгоритмах O (1) размера O (n) времени?

Для меня вы можете применять эту технику всякий раз, когда вам нужно вычислить свойство P для последовательности элементов, которая:

  1. может быть увеличено с seq[n, m] до seq[n, m+1] за O (1) раз, если Q(seq[n, m+1]) не удерживает
  2. P(seq[n, m]) может быть вычислено в O (1) времени и пространстве от P(seq[n, j]) и P(seq[j, m]), если Q(seq[n, j]) содержит

В нашем случае P - это «лишние» вхождения нашего «избранного» основного элемента, а Q - это «P - ноль».

Если вы видите вещи таким образом, самая длинная общая подпоследовательность использует ту же идею (не знаю о ее "коэффициенте крутости";))

4 голосов
/ 24 мая 2011

У Джайдева Мисры и Дэвида Гриса есть документ под названием Поиск повторяющихся элементов ( ACM page ), который обобщает его на элемент, повторяющийся более чем в n / k раз (k = 2 - этопроблема большинства).

Конечно, это, вероятно, очень похоже на исходную проблему, и вы, вероятно, ищете «другие» алгоритмы.

Вот пример, который, возможно, отличается.

Дайте алгоритм, который будет определять, правильно ли сформирована строка скобок ('(' и ')').

Я считаю, что стандартное решение состоит в том, чтобы поддерживать счетчик.

Примечание:

Что касается ответов, утверждение которых не может быть постоянным пробелом и т. Д., Спросите их омодель расчета.Например, в модели WORD RAM вы предполагаете, что целые числа / индексы массива и т. Д. Равны O (1).

Многие люди неправильно смешивают и подбирают модели.Например, у них, к счастью, будет входной массив из n целых чисел, равный O (n), индекс массива, равный пробелу O (1), но счетчик, который они считают Omega (log n) и т. Д., Что является бессмысленным.Если они хотят учесть размер в битах, то сам ввод Omega (n log n) и т. Д.

2 голосов
/ 27 марта 2016

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

Здесь я опишу естественное расширение этого алгоритма (илиобобщение).Таким образом, в стандартном алгоритме большинства голосов вы должны найти элемент, который появляется в потоке не менее n/2 раз, где n - размер потока. Вы можете сделать это в O(n)время (с крошечной константой и в O(log(n)) пространстве, в худшем случае и крайне маловероятно.

Обобщенный алгоритм позволяет найти k наиболее частых предметов, где каждый раз появлялся вминимум n/(k+1) раз в исходном потоке. Обратите внимание, что если k = 1, вы в конечном итоге столкнетесь с исходной проблемой.

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

Как и для исходного большинства vПри использовании алгоритма голосования вам необходимо иметь гарантию, что у вас есть эти k мажоритарных элементов, в противном случае вам придется сделать еще один проход по массиву, чтобы убедиться в правильности ранее найденных возможных элементов.Вот моя попытка Python (не провел тщательное тестирование). 

from collections import defaultdict
def majority_element_general(arr, k=1):
    counter, i = defaultdict(int), 0
    while len(counter) < k and i < len(arr):
        counter[arr[i]] += 1
        i += 1

    for i in arr[i:]:
        if i in counter:
            counter[i] += 1
        elif len(counter) < k:
            counter[i] = 1
        else:
            fields_to_remove = []
            for el in counter:
                if counter[el] > 1:
                    counter[el] -= 1
                else:
                    fields_to_remove.append(el)
            for el in fields_to_remove:
                del counter[el]

    potential_elements = counter.keys()
    # might want to check that they are really frequent.
    return potential_elements
...