Название устанавливает вопрос.
В качестве входных данных у нас есть список элементов, которые мы можем сравнить (определить, какой из них больше ). Ни один элемент не может быть равным.
Ключевые моменты:
- Сравнение не является транзитивным (подумайте о бумажных ножницах): это может быть правдой: A> B, B> C, C> A (обратите внимание, что это неверный ввод, поскольку здесь нет правильного ответа, я только описываю, что " «нетранзитивное сравнение» означает)
- Каждый входной массив будет гарантированно иметь ответ
- Наибольшее означает, что элемент должен быть больше, чем любой другой элемент
- Имеет место обратное свойство, т.е. 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).
Я зацикливаюсь на каждом подходе из-за того факта, что для уверенности в ответе элемент необходимо явно сравнить с любым другим элементом, чтобы доказать, что это действительно ответ (потому что сравнение не транзитивно).
Это исключает использование кучи, сортировки и т. Д.
algorithms
time-complexity
sets
transitivity
Джеймс Вежба
источник
источник
Ответы:
Стандартный алгоритм поиска максимума все еще работает. Начните с и перейти на элементы, если вы видите , большее значение, обновить максимум , чтобы быть этим значением. Это работает потому, что каждый пропущенный элемент меньше, чем хотя бы один элемент, и поэтому не может быть максимальным.a1
Чтобы быть понятным, под «стандартным алгоритмом» я имею в виду следующее:
Для полноты, я буду обсуждать здесь вопросы, поднятые в комментариях. Настройка в приведенном выше обсуждении заключается в нахождении максимума относительно антисимметричного отношения , где a i является максимумом, если для всех j ≠ i мы имеем a i > a j . Вышеприведенный алгоритм работает в предположении, что максимум существует, однако, если он не известен, его можно использовать для проверки существования максимума (проверьте, действительно ли возвращаемый элемент больше, чем все другие элементы, это упоминается в комментарии Чи а в илмари каронен отвечу).< aя J ≠ я aя> аJ
Если не обязательно антисимметрично, то вышеприведенный алгоритм не работает (как Эмиль упоминал в комментариях). Если < произвольное соотношение (т.е. мы ослабляем как транзитивность, так и антисимметрию), то нетрудно показать, что нахождение максимума за линейное время невозможно. Обозначим # a i, сколько раз a i участвовал в запросе, мы определяем состязательное отношение таким образом, что максимум не может быть выявлен без достаточного количества запросов. Учитывая запрос а я > ? a j , ответьте a i > a j, если # a i< < # aя aя aя> ? J aя> аJ и a i < a j в противном случае. Если количество запросов равно o ( n 2 ) , то максимум еще не был замечен, и его можно установить как любой из элементов в наборе.# aя< n - 1 aя< аJ о ( n2)
источник
n
сравнений ваш текущий максимум должен быть ответомmax
мог быть только максимум подмассива. Тем не менее, даже без предположения 2, можно найти предварительный максимум, а затем проверить его на всем массиве с помощью второго сканирования в пределах O (n).Как отмечает Ариэль , стандартный алгоритм максимального поиска приведен ниже:
фактически будет работать без изменений, пока:
(Первое предположение выше может быть фактически ослаблено, даже без необходимости изменять алгоритм, если мы предполагаем, что максимальный элемент сопоставим с любым другим элементом, и это
x > y
всегда ложно, если элементыx
иy
несопоставимы.)В частности, вы утверждаете, что:
неверно в предположениях, приведенных выше. Фактически, чтобы доказать, что приведенный выше алгоритм всегда найдет максимальный элемент, достаточно заметить, что:
x
будет максимальный элемент;m
будет максимальный элемент; иm
он не изменится ни на одной из последующих итераций.Следовательно, в конце цикла
m
всегда будет максимальный элемент, если вход содержит один элемент.Ps. Если входные данные не обязательно всегда содержат максимальный элемент, то проверка этого факта действительно потребует проверки ответа кандидата на каждый другой элемент, чтобы убедиться, что он действительно максимальный. Тем не менее, мы можем сделать это за O ( n ) время после запуска алгоритма максимального нахождения выше:
(Здесь я предполагаю, что отношение
>
нерефлексивно, то есть ни один элемент не может быть больше самого себя. Если это не обязательно так, сравнениеx > m
на шаге 2 следует заменить наx ≠ m and x > m
, где≠
обозначает сравнение идентичности. Или мы могли бы просто применить оптимизацию отмечено ниже.)Чтобы доказать правильность этого варианта алгоритма, рассмотрим два возможных случая:
m
. Неважно, какой это элемент, так как он в любом случае будет не максимальным, и поэтому шаг 2 обнаружит это и вернетNone
.Если мы сохранили индекс
m
в входном массивеa
, мы могли бы на самом деле оптимизировать шаг 2 , чтобы проверить только те элементы , которые приходят , прежде чемm
в памятиa
, поскольку любые последующих элементы уже по сравнению сm
в шаге 1. Но эта оптимизация не изменяет асимптотическую сложность времени алгоритма, который по-прежнему O ( n ).источник
if x > m:
оно не определено.Если вы просматриваете список сравнения элементов, любой элемент, который «теряет» сравнение, может быть немедленно отброшен, так как для того, чтобы быть наибольшим, он должен быть больше, чем ВСЕ другие элементы, поэтому единственная потеря дисквалифицирует его.
Это решение обеспечивается тонкостью: «Ни один элемент не может быть равным» в сочетании с тем фактом, что всегда будет самый большой элемент. Если мы отобразим отношения выигрышей в виде ориентированного графа, ясно, что мы можем достичь наибольшего элемента, просто следуя победам.
источник
Я предполагаю, что отношение антисимметрично хотя бы для одного элемента (что гарантирует существование наибольшего элемента), в противном случае задача невозможна. Если все элементы в конечном множестве сравнимы, то работает обычная процедура нахождения максимума.
Если некоторые элементы не сопоставимы, то будет работать следующая процедура
источник
else if
необходимо. Он не может быть запущен, еслиmax
является максимумом, и если максимум еще не достигнут, не имеет значения, каково значениеmax
.if
s безelse
s? Это просто привычка: сelse
s мы даже не сравниваем. :)max
какой-либо элемент списка и сделать это внутри циклаif max and a[i] are comparable and max < a[i] then max = a[i]
(где первая часть условия может быть опущена, если мы предположим, что попытка сравнить два несопоставимых элемента всегда приводит к ложному результату)?Надеюсь, это несколько понятно. Не стесняйтесь спрашивать в комментариях или редактировать.
Основная идея заключается в том, что вы не можете собрать какую-либо информацию об оставшихся элементах из уже известных вам, если разрешите совершенно произвольное отношение.
источник
A > B
источник