На этом шаге мы рассмотрим, какой элемент списка называется мажоритарным и приведем рекурсивную функцию, осуществляющую его поиск.

Говорят, что в списке есть "мажоритарный элемент" (или доминирующий, преобладающий), если более половины его элементов одинаковы. В этой классической задаче цель состоит в том, чтобы выяснить, есть ли в списке длины n мажоритарный элемент, и, если есть, найти его. Кроме того, задача предполагает, что элементы сравниваются за (постоянное) время Θ(1) при использовании операции сравнения (==). Иными словами, запрещаются сравнения <, >, ≤ или ≥ (в примерах будут использоваться только целочисленные операции).

Для решения задачи существует несколько вариантов применения принципа "разделяй и властвуй". Мы рассмотрим метод, возвращающий кортеж (или список) из трёх значений:

(1) признак "содержит ли список мажоритарный элемент" (логическая переменная);
(2) мажоритарный элемент, если он есть. Иначе это значение не определено (функция может просто вернуть None);
(3) количество вхождений мажоритарного элемента (0, если его нет).

Размер задачи - n. Первое начальное условие может соответствовать пустому списку, результатом которого был бы кортеж (False, x, 0), где значение x не определено. Кроме того, если список содержит один элемент, функция должна вернуть (True, a₀, 1).

Рекурсивное условие выводится путём деления списка пополам и решения соответствующих подзадач. Чтобы понять, как объединить решения подзадач, построим на конкретном примере начальные рекурсивные схемы. Например:

В этом конкретном случае результат обеих подзадач - False. Это значит, что входной список не содержит мажоритарного элемента (хотя список содержит ровно n/2 вхождений элемента 4, этого недостаточно для истинного результата). Вообще, это можно доказать следующим образом. Сначала исходный список делится пополам (независимо от чётности n, так как n = ⌊n/2⌋ + ⌊n/2⌋ на два подсписка - b длины ⌊n/2⌋ и c длины ⌊n/2⌋. Если результат обеих подзадач - False, то элемент может появиться не более ⌊⌊n/2⌋/2⌋ в b и ⌊⌊n/2⌋/2⌋ раз в с. Сложение этих величин даёт:

    ⌊⌊n/2⌋/2⌋ + ⌊⌊n/2⌋/2⌋ < (⌊n/2⌋ + ⌊n/2⌋) / 2 = n/2 ≤ n/2.

Отсюда можно заключить, что элемент не может появиться в исходном списке более n/2 раз.

Схема для другого конкретного примера могла бы быть такой:

В этом случае элемент 4 трижды появляется в первом подсписке и потому является мажоритарным, так как 3 > n/2 = 2. Поэтому алгоритм должен посчитать число вхождений 4 во второй подсписок (обозначенный #(с, 4)), чтобы определить, является ли он мажоритарным для исходного списка а. Это можно сделать с помощью простой линейно-рекурсивной функции (см. пример 6.6), получающей на входе список а и элемент х. Если а пуст, результат, очевидно, 0. В противном случае результатом будет вызов метода, который применяется к хвосту списка a (а_{1...n - 1}) и х (плюс единица, если а₀ = х).

Пример 6.6. Подсчёт количества элементов в списке

1
2
3
4
5

def occurrences_in_list(a, x):
    if a == []:
        return 0
    else:
        return int(a[0] == x) + occurrences_in_list(a[1:], x)

Архив с файлом можно взять здесь.

В примере 6.7 приводится возможная реализация функции, решающей задачу поиска мажоритарного элемента. Начальные условия - в строках 3 - 6. Строки 8 и 9 делят входной список пополам. Строка 11 вызывает метод для первого подсписка, и если в нём есть мажоритарный элемент (строка 12), то вычисляется количество вхождений этого элемента во второй подсписок (строка 13). Если общее количество вхождений элемента (в двух подсписках) больше n/2 (строка 14), метод возвращает кортеж (строка 15) со значениями (True, мажоритарный элемент, количество появлений во входном списке). Строки 17-21 аналогичны, но меняют списки ролями. Наконец, если функция не вернула результат, то список вообще не содержит мажоритарного элемента (строка 23).

В рекурсивных условиях метод должен вызвать себя дважды для каждой половины входного списка, а также вычислить количество вхождений элемента в оба подсписка длиной (примерно) n/2. Поскольку эта последняя вспомогательная функция выполняется за линейное время, временная сложность метода может быть оценена функцией

            1,           если n ≤ 1,
    T(n) =  
            T(n/2) + cⁿ, если n > 1,

Таким образом, временная сложность алгоритма - порядка Θ(n logn) (см. (3.28)). В заключение добавим, что эта задача может быть решена за линейное время с помощью алгоритма "большинства голосов" Бойера-Мура (Boyer-Moore majority vote algorithm).

Пример 6.7. Решение задачи о мажоритарном элементе

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

def majority_element_in_list(a):
    n = len(a)
    if n == 0:
        return (False, None, 0)
    elif n == 1:
        return (True, a[0], 1)
    else:
        b = a[0:n // 2]
        c = a[n // 2:n]
        t = majority_element_in_list(b)
        if t[0]:
            occurrences = occurrences_in_list(c, t[1])
            if t[2] + occurrences > n / 2:
                return (True, t[1], t[2] + occurrences)    

        t = majority_element_in_list(c)
        if t[0]:
            occurrences = occurrences_in_list(b, t[1])
            if t[2] + occurrences > n / 2:
                return (True, t[1], t[2] + occurrences)    

        return (False, None, 0)

Архив с файлом можно взять здесь.

На следующем шаге мы рассмотрим быстрое целочисленное умножение.

Предыдущий шаг Содержание Следующий шаг