за время O (n): найти наибольший элемент в наборе, где сравнение не транзитивно

21

Название устанавливает вопрос.

В качестве входных данных у нас есть список элементов, которые мы можем сравнить (определить, какой из них больше ). Ни один элемент не может быть равным.

Ключевые моменты:

  1. Сравнение не является транзитивным (подумайте о бумажных ножницах): это может быть правдой: A> B, B> C, C> A (обратите внимание, что это неверный ввод, поскольку здесь нет правильного ответа, я только описываю, что " «нетранзитивное сравнение» означает)
  2. Каждый входной массив будет гарантированно иметь ответ
  3. Наибольшее означает, что элемент должен быть больше, чем любой другой элемент
  4. Имеет место обратное свойство, т.е. A> B означает, что B <A

Пример:

Input: [A,B,C,D]
A > B, B > C, C > A
D > A, D > B, D > C
Output: D

Я не могу найти способ сделать это за O (n), мое лучшее решение - O (n ^ 2).

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

Это исключает использование кучи, сортировки и т. Д.

Джеймс Вежба
источник
8
Неясно, как будет определен «величайший элемент»? Например, какой элемент является наибольшим, если ? Есть ли у вас другие правила сравнения? A>B,B>C,C>A
fade2black
6
Я не представляю, как бы мы выбрали самый большой элемент в наборе, который хотя бы частично не упорядочен. Пожалуйста, посмотрите определение самого большого и наименьшего элемента. Отсутствие транзитивности исключает частичный порядок.
fade2black
3
@ fade2black Почему вы связываете меня с другим определением "величайшего". Я в явном виде излагаю определение величайшего для контекста этого вопроса. Величайшее означает, что элемент больше, чем любой другой элемент. Ни один элемент не равен. Это все, что нужно сделать. Разве это не ясно?
Джеймс Вежба
2
Ваш последний пример с A, B, C, D будет полезен для понимания вашего вопроса, если вы включили его в свой OP.
fade2black
3
Член команды компилятора C # обычно задавал это как вопрос для интервью; это актуально, потому что в C # алгоритм разрешения перегрузки должен выбирать уникальный лучший член набора с учетом отношения «лучшего качества», которое обычно, но не обязательно, является транзитивным. (Или дать подходящий ответ, если такого уникального лучшего участника нет; связи возможны.) Хотя мне удалось ответить на него правильно, я никогда не думал, что это был особенно хороший вопрос для интервью, поскольку он опирается на понимание "ага", чтобы получить линейный алгоритм
Эрик Липперт

Ответы:

38

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

Чтобы быть понятным, под «стандартным алгоритмом» я имею в виду следующее:

max <- a_1
for i=2 to n
   if a_i > max
      max <- a_i
output max

Для полноты, я буду обсуждать здесь вопросы, поднятые в комментариях. Настройка в приведенном выше обсуждении заключается в нахождении максимума относительно антисимметричного отношения , где a i является максимумом, если для всех j i мы имеем a i > a j . Вышеприведенный алгоритм работает в предположении, что максимум существует, однако, если он не известен, его можно использовать для проверки существования максимума (проверьте, действительно ли возвращаемый элемент больше, чем все другие элементы, это упоминается в комментарии Чи а в илмари каронен отвечу).<aяJяaя>aJ

Если не обязательно антисимметрично, то вышеприведенный алгоритм не работает (как Эмиль упоминал в комментариях). Если < произвольное соотношение (т.е. мы ослабляем как транзитивность, так и антисимметрию), то нетрудно показать, что нахождение максимума за линейное время невозможно. Обозначим # a i, сколько раз a i участвовал в запросе, мы определяем состязательное отношение таким образом, что максимум не может быть выявлен без достаточного количества запросов. Учитывая запрос а я > ? a j , ответьте a i > a j, если # a i<<#aяaяaя>?aJaя>aJ и a i < a j в противном случае. Если количество запросов равно o ( n 2 ) , то максимум еще не был замечен, и его можно установить как любой из элементов в наборе.#aя<N-1aя<aJо(N2)

Ariel
источник
1
@JamesWierzba (я думаю) он просто означает, что «пропущенный» элемент - это элемент, который не превышает ваш текущий максимум. Рассмотрим стандартный алгоритм: вы проверяете каждое значение в вашем списке по текущему максимуму. Вы сказали, что в каждом списке есть величайший элемент. В какой-то момент вы сравните это с вашим текущим максимумом, и, поскольку он больше, это значение станет вашим новым максимумом. Поскольку это значение больше, чем все остальное в списке, вы никогда не найдете элемент, который больше, и ваше наибольшее значение не будет заменено. После ваших nсравнений ваш текущий максимум должен быть ответом
лорд Фаркуаад
1
Отредактированный для ясности, этот алгоритм не предполагает транзитивность. Если вам трудно в это поверить, следуйте деталям доказательства корректности (предположим, что в целях противоречия возвращаемое значение не является максимальным, и используйте идею из первого абзаца).
Ариэль
7
Это зависит от предположения 2 в вопросе: в массиве всегда есть максимум. Если бы это было не так, maxмог быть только максимум подмассива. Тем не менее, даже без предположения 2, можно найти предварительный максимум, а затем проверить его на всем массиве с помощью второго сканирования в пределах O (n).
Чи
7
Этот ответ предполагает, что и B > A не могут удерживаться одновременно. Насколько я вижу, это не исключено в этом вопросе. A>ВВ>A
Эмиль Йержабек поддерживает Монику
4
@ oconnor0 Это не следует. Для конкретного примера предположим, что A> B, A> C, B> A и C> B. Тогда A больше, чем любой другой элемент в наборе (и является единственным элементом с этим свойством), но если элементы встречаются в порядке A, B, C, алгоритм выдаст C.
Эмиль Йержабек поддерживает Monica
24

Как отмечает Ариэль , стандартный алгоритм максимального поиска приведен ниже:

def find_maximum(a):
    m = a[0]
    for x in a:
        if x > m: m = x
    return m

фактически будет работать без изменений, пока:

  • любую пару элементов можно сравнить, и
  • вход гарантированно содержит максимальный элемент, то есть элемент, попарно превышающий любой другой элемент на входе.

(Первое предположение выше может быть фактически ослаблено, даже без необходимости изменять алгоритм, если мы предполагаем, что максимальный элемент сопоставим с любым другим элементом, и это x > yвсегда ложно, если элементы xи yнесопоставимы.)

В частности, вы утверждаете, что:

[…] Чтобы быть уверенным в ответе, этот элемент необходимо явно сравнивать с любым другим элементом (поскольку сравнение не является транзитивным).

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

  1. поскольку цикл перебирает все входные элементы, на некоторой итерации xбудет максимальный элемент;
  2. поскольку максимальный элемент попарно больше, чем любой другой элемент, из этого следует, что в конце этой итерации mбудет максимальный элемент; и
  3. поскольку никакой другой элемент не может быть попарно больше максимального элемента, из этого следует, что mон не изменится ни на одной из последующих итераций.

Следовательно, в конце цикла mвсегда будет максимальный элемент, если вход содержит один элемент.


Ps. Если входные данные не обязательно всегда содержат максимальный элемент, то проверка этого факта действительно потребует проверки ответа кандидата на каждый другой элемент, чтобы убедиться, что он действительно максимальный. Тем не менее, мы можем сделать это за O ( n ) время после запуска алгоритма максимального нахождения выше:

def find_maximum_if_any(a):
    # step 1: find the maximum, if one exists
    m = a[0]
    for x in a:
        if x > m: m = x

    # step 2: verify that the element we found is indeed maximal
    for x in a:
        if x > m: return None  # the input contains no maximal element
    return m  # yes, m is a maximal element

(Здесь я предполагаю, что отношение >нерефлексивно, то есть ни один элемент не может быть больше самого себя. Если это не обязательно так, сравнение x > mна шаге 2 следует заменить на x ≠ m and x > m, где обозначает сравнение идентичности. Или мы могли бы просто применить оптимизацию отмечено ниже.)

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

  • Если вход содержит максимальный элемент, то шаг 1 найдет его (как показано выше), а шаг 2 подтвердит его.
  • Если входные данные не содержат максимальный элемент, то шаг 1 в итоге выберет некоторый произвольный элемент как m. Неважно, какой это элемент, так как он в любом случае будет не максимальным, и поэтому шаг 2 обнаружит это и вернет None.

Если мы сохранили индекс mв входном массиве a, мы могли бы на самом деле оптимизировать шаг 2 , чтобы проверить только те элементы , которые приходят , прежде чем mв памяти a, поскольку любые последующих элементы уже по сравнению с mв шаге 1. Но эта оптимизация не изменяет асимптотическую сложность времени алгоритма, который по-прежнему O ( n ).

Илмари Каронен
источник
3
На самом деле ОП пропускает много деталей. Например, ничего не сказано о рефлексивности отношения, и поэтому, если оно не рефлексивно, то if x > m:оно не определено.
fade2black
4

О(N)

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

N-1

Это решение обеспечивается тонкостью: «Ни один элемент не может быть равным» в сочетании с тем фактом, что всегда будет самый большой элемент. Если мы отобразим отношения выигрышей в виде ориентированного графа, ясно, что мы можем достичь наибольшего элемента, просто следуя победам.

Данилов
источник
1
« Ациклический ориентированный граф » - неправильная модель: вместо этого он должен быть « турниром ». Циклы разрешены, и важно, чтобы каждое ребро существовало ровно в одном направлении.
Питер Тейлор
@PeterTaylor вы абсолютно правы, я думал только о победах, которые ведут к «величайшему» элементу, другие победы менее значимы, но могут быть пройдены на пути к обнаружению величайшего, поэтому вы правы, что они могут » не стоит сбрасывать со счетов
Даников
3

Я предполагаю, что отношение антисимметрично хотя бы для одного элемента (что гарантирует существование наибольшего элемента), в противном случае задача невозможна. Если все элементы в конечном множестве сравнимы, то работает обычная процедура нахождения максимума.

Если некоторые элементы не сопоставимы, то будет работать следующая процедура

max = nil
For i=1 to n
   if max is nil then
      max = a[i]
   if max and a[i] are not comparable then
      max = nil
   else if max < a[i] then
      max = a[i]
End

A,В,С,D

A>В,В>С,С>A
D>A,D>В,D>С


язнак равно1: Максимумзнак равноA
язнак равно2: Максимумзнак равноAA>В
язнак равно3: Максимумзнак равноСA<С
язнак равно4: Максимумзнак равноDD>С

м>aa<мaмм<aaмaм

fade2black
источник
Я не думаю, что первое else ifнеобходимо. Он не может быть запущен, если maxявляется максимумом, и если максимум еще не достигнут, не имеет значения, каково значение max.
Ричи
Да, это первый. Другой второй :)
rici
Вы имеете в виду оставить ifs без elses? Это просто привычка: с elses мы даже не сравниваем. :)
fade2black
1
Разве не проще было бы просто инициализировать maxкакой-либо элемент списка и сделать это внутри цикла if max and a[i] are comparable and max < a[i] then max = a[i](где первая часть условия может быть опущена, если мы предположим, что попытка сравнить два несопоставимых элемента всегда приводит к ложному результату)?
Ильмари
1
@badallen ОП предполагает, что всегда есть величайший элемент. В вашем примере нет величайшего элемента.
fade2black
2

A<BB<A

A1,,,ANAя<AJ

N2

Aя<AJJ

J0Aя<AJ0яJяJAя<AJяяJAяJ<AJJ0яJ

Надеюсь, это несколько понятно. Не стесняйтесь спрашивать в комментариях или редактировать.

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

A<ANN2-N

Коринна
источник