Я хочу доказать или опровергнуть существование алгоритма, который, учитывая массив целых чисел, находит три индекса i , j и k такие, что i < j < k и A [ i ] < A [ j ] < A [ k ] (или находит, что такой тройки не существует) за линейное время.
Это не домашнее задание; Я видел это на форуме по программированию под названием «попытаться реализовать такой алгоритм». Я подозреваю, что это невозможно после различных экспериментов. Моя интуиция говорит мне об этом, но это ничего не значит.
Я хотел бы доказать это формально. Как ты делаешь это? В идеале я хотел бы, чтобы пошаговое доказательство выкладывалось постепенно, а затем, если вы так склонны, дать какое-то объяснение о том, как поступить с доказательством / опровержением простых вопросов, подобных этому в целом. Если это поможет, несколько примеров:
[1,5,2,0,3] → (1,2,3)
[5,6,1,2,3] → (1,2,3)
[1,5,2,3] → (1,2,3)
[5,6,1,2,7] → (1,2,7)
[5,6,1,2,7,8] → (1,2,7)
[1,2,999,3] → (1,2,999)
[999,1,2,3] → (1,2,3)
[11,12,8,9,5,6,3,4,1,2,3] → (1,2,3)
[1,5,2,0,-5,-2,-1] → (-5,-2,-1)
Я предположил, что можно итерировать по , и каждый раз, когда существует i < j (то есть наш текущий j ), мы создаем новую тройку и помещаем ее в массив. Мы продолжаем шагать и сравнивать каждую тройку, пока одна из наших тройок не будет завершена. Так как , ! Но я думаю, что это сложнее, чем просто O ( n ), так как количество троек в нашем тройном массиве в худшем случае будет соответствовать размеру входного списка.[1,5,2,0,-5,-2,-1] → 1..2.. -5.. -2.. -1
[1,5,2,0,-5,-2,3,-1] → 1..2.. -5.. -2.. 3
источник
Ответы:
Это вариация самой длинной возрастающей проблемы подпоследовательности ; это решение, представленное в Википедии с использованием двух вспомогательных массивов и P :M п
Этот алгоритм работает в наихудшее время . Ваша проблема - это особый случай, который позволяет вам вернуться, когда L = 3, что понижает время выполнения до O ( n ), потому что бинарный поиск выполняется только по массивам длиной не более двух, что, следовательно, во времени O ( 1 ), а не Θ ( журнал п ) в общем случае.Θ(nlogn) L=3 O(n) O(1) Θ(logn)
Рассмотрим модифицированный псевдокод:
источник
Примечание о методологии
Я немного подумал об этой проблеме и пришел к решению. Когда я прочитал ответ Саида Амири , я понял, что я разработал специализированную версию стандартного алгоритма поиска самой длинной подпоследовательности для последовательности длины 3. Я публикую сообщение о том, как я нашел решение, потому что я думаю, что оно интересный пример решения проблем.
Двухэлементная версия
Этот случай очень прост; мы постараемся обобщить это. Это показывает, что заявленная проблема не решаема: запрошенные индексы не всегда существуют. Поэтому мы скорее спросим, что алгоритм либо возвращает действительные индексы, если они существуют, либо правильно утверждает, что таких индексов не существует.
Подойдя к алгоритму
Мы только что увидели, что запрошенные индексы не всегда существуют. Наша стратегия состоит в том, чтобы учиться, когда индексы не существуют. Мы сделаем это, предположив, что мы пытаемся найти индексы и увидим, как наш поиск может пойти не так. Тогда случаи, когда поиск не идет не так, предоставят алгоритм для поиска индексов.
Постановка алгоритма
Приведено в синтаксисе Python, но учтите, что я его не проверял.
Эскиз доказательства
index1
является индексом минимума части массива, которая уже была пройдена (если это происходит несколько раз, мы сохраняем первое вхождение) илиNone
перед обработкой первого элемента.index2
хранит индексы возрастающей подпоследовательности длины 2 в уже пройденной части массива, который имеет наименьший наибольший элемент, или,None
если такая последовательность не существует.Когда
return (index2[0], index2[1], i)
работает, мы имеемvalue2[0] < value[1]
(это инвариантvalue2
) иvalue[1] < A[i]
(очевидно из контекста). Если цикл заканчивается без вызова досрочного возврата, тоvalue1 == None
в этом случае нет увеличивающейся подпоследовательности длины 2, не говоря уже о 3, илиvalue1
содержит возрастающую подпоследовательность длины 2, которая имеет самый низкий самый большой элемент. В последнем случае, кроме того, у нас есть инвариант, что никакая возрастающая подпоследовательность длины 3 не заканчивается раньше, чемvalue1
; следовательно, последний элемент любой такой подпоследовательности, добавленный кvalue2
, будет формировать возрастающую подпоследовательность длины 3: поскольку у нас также есть инвариант, которыйvalue2
не является частью увеличивающейся подпоследовательности длины 3, содержащейся в уже пройденной части массива, нет такой подпоследовательности во всем массиве.Доказательство вышеупомянутых инвариантов оставлено в качестве упражнения для читателя.
сложность
Формальное доказательство
Оставлено в качестве упражнения для читателя.
источник
Во-первых, просмотрите массив слева направо, поддерживая стек и вспомогательный массив, который сообщает вам для каждого элемента, индекс элемента больше его и справа от него.
Каждый раз, когда вы рассматриваете новый элемент в массиве, если этот элемент больше, чем верхний элемент стека, вы извлекаете его из стека и устанавливаете для элемента массива aux, соответствующего верхнему, индекс нового элемента ниже рассмотрение.
Продолжайте выталкивать элементы из стека и устанавливать соответствующий индекс, пока текущий элемент больше. Как только у вершины есть элемент, который не меньше (или становится пустым), поместите текущий элемент в стек и перейдите к следующему элементу массива, повторяя вышеуказанный шаг.
Сделайте еще один проход (и еще один вспомогательный массив), но двигайтесь справа налево.
Псевдокод для первого прохода может выглядеть так:
источник