9.2. Поиск доминирующего элемента

В этом параграфе вы познакомитесь с улучшенной версией одного из самых популярных алгоритмов сортировки — быстрой сортировки. Вы узнаете, как адаптировать её под случаи с большим числом повторяющихся элементов и как добиться устойчивого времени выполнения даже на «неудобных» входах.

Ключевые вопросы параграфа

• Почему стандартная быстрая сортировка может работать медленно на массивах с повторяющимися элементами?
• Как изменить алгоритм так, чтобы избежать деградации производительности?
• Как реализовать трёхчастное разбиение и почему оно даёт прирост в эффективности?

Проверка последовательности

Ваша задача — проверить, содержит ли данная последовательность элемент, который встречается более половины раз.

• Формат ввода: Первая строка содержит целое число , следующая — последовательность целых неотрицательных чисел .
• Формат вывода: Выведите , если в последовательности содержится элемент, который встречается больше, чем раз, и в противном случае.
• Ограничения: ; для всех .
• Примеры:

Пример 1

Пример 2

• В первом примере — доминирующий элемент.
• Во втором примере у последовательности нет доминирующего элемента. Обратите внимание, что элемент — не доминирующий.

Решение

Здесь приведён примитивный алгоритм, который решает задачу «Поиск доминирующего элемента» за квадратичное время:

1MajorityElement(A[1..n]):
2    for i from 1 to n:
3        currentElement = A[i]
4        count = 0
5        for j from 1 to n:
6            if A[j] = currentElement:
7                count = count + 1
8        if count > n/2:
9            return 1
10    return 0

На практике входную последовательность можно просканировать и сохранить число вхождений каждого элемента в ассоциативном массиве. Время выполнения этого решения зависит от конкретной реализации ассоциативного массива. Если реализация представляет собой сбалансированное дерево поиска, тогда каждый уточняющий запрос в массиве занимает , а общее время выполнения составляет . Для хеш-таблиц уточняющие запросы эффективны на практике, хотя и могут варьироваться в зависимости от вводных данных.

Стратегия «Разделяй и властвуй»

Стратегия «разделяй и властвуй» приводит к простому алгоритму с временем выполнения . Несложная, но невероятно важная вещь: если — это доминирующий элемент последовательности, тогда должен быть доминирующим элементом как минимум в одной из половин.

Однако обратите внимание, что обратное неверно: обе половины последовательности содержат доминирующие элементы ( и соответственно), но ни один из них не является доминирующим элементом изначальной последовательности.

Это приводит нас к следующему алгоритму: найти доминирующий элемент в обоих половинах с помощью рекурсии и для каждой из половин проверить количество вхождений в изначальную последовательность.

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

Упражнение

Сможете ли вы спроектировать еще более быстрый алгоритм с временем выполнения ? В основе лежит следующая идея. Разделить вводные элементы на пары. Рассмотреть каждую пару: если два элемента различны, отбросить оба; в противном случае отбросить один из них.

Что дальше

Теперь вы умеете модифицировать быструю сортировку так, чтобы она работала эффективно даже на массивах с повторяющимися элементами. Вы узнали, как устроено трёхчастное разбиение, и научились избегать худших случаев, когда обычная реализация деградирует до квадратичного времени.

Далее — задача на подсчёт инверсий. Вы увидите, как можно сочетать сортировку и рекурсию, чтобы решать аналитические задачи быстрее, чем простым перебором.

А пока вы не ушли дальше — закрепите материал на практике:

• Отметьте, что урок прочитан, при помощи кнопки ниже.
• Пройдите мини-квиз, чтобы проверить, насколько хорошо вы усвоили тему.
• Перейдите к задачам этого параграфа и потренируйтесь.
• Перед этим — загляните в короткий гайд о том, как работает система проверки.

Хотите обсудить, задать вопрос или не понимаете, почему код не работает? Мы всё предусмотрели — вступайте в сообщество Хендбука! Там студенты помогают друг другу разобраться.

Ключевые выводы параграфа

• Стратегия «Разделяй и властвуй» позволяет находить доминирующий элемент за , разбивая задачу на части.
• Элемент считается доминирующим, если он встречается больше чем в половине элементов последовательности.
• Проверки в обеих половинах не гарантируют общий результат — требуется финальное сканирование.
• Можно спроектировать и более быстрый алгоритм за , если использовать идею попарного сравнения и отбрасывания.