Как использовать аргументы противника для выбора и сортировки вставки?

Question

Меня попросили найти аргументы противника, необходимые для поиска нижних границ для выбора и вставки. Я не мог найти ссылку на это нигде.

У меня есть некоторые сомнения в этом. Я понимаю, что аргументы противника обычно используются для поиска нижних границ для определенных «проблем», а не «алгоритмов».

Я понимаю проблему слияния. Но как я мог написать один для выбора и вставки?

Answer 1

Из вашего комментария кажется, что вы сбиваете с толку значение нижних границ, верхних границ и асимптотических обозначений. Например, возьмите вставку. Его лучшим временем работы является $ theta (n) $ (это происходит, когда вход уже отсортирован). Его наихудшее время выполнения-$ theta (n^2) $ (это происходит, когда ввод сортируется). Таким образом, поскольку время выполнения падает между линейной функцией $ n $ и квадратичной функцией $ n $, вы можете сказать, что время выполнения вставки составляет как $ Omega (n) $, так и $ O (n^2 ) $. В этом случае важно понимать, что вы не может Скажите, что время выполнения $ omega (n^2) $. Почему? Потому что существует вход, который приводит к тому, что алгоритм работает в $ O (n) $. Тем не менее, вы можете сказать, что наихудшее время выполнения-$ Omega (n^2) $, опять же, потому что существует вход, который приводит к запуску алгоритма в $ Omega (n^2) $. Мы обычно используем нотацию $ o $ для наихудшего случая, поскольку мы заинтересованы в верхней границе по количеству операций, выполняемых алгоритмом.

Теперь давайте подумаем о аргументе противника для вставки (вы можете попытаться вывести один для выбора, применяя те же идеи).

Рассмотрим алгоритм сортировки вставки, играющий против противника, который мы будем называть противником. Целью противника является предоставление ввода X для алгоритма, который максимизирует количество сравнений, проведенных алгоритмом. Это обычно анализируется в контексте Деревья решения. Анкет Дерево решений показывает все возможные последовательности сравнений, которые может провести алгоритм. Каждый внутренний узел дерева решений представляет собой единое сравнение. Двое детей узла представляют два результата сравнения (да/нет или верно/false). Каждый лист представляет возможный выход. Для алгоритмов сортировки листья перестановки ключей. Алгоритм начинается с корня и следует по пути к листу. На каждом внутреннем узле ответ на сравнение, сделанное, рассказывает об алгоритме, какой узел должен быть посещен далее. Когда алгоритм достигает листа, он выводит соответствующую перестановку. Время выполнения алгоритма (рассматриваемое как дерево решений) для данного входа - это количество сравнений, проведенных на пути от корня до выходного листа. Теперь у противника есть простая стратегия, которая будет работать с любым алгоритмом сортировки на основе сравнения, включая сортировку вставки: всякий раз, когда алгоритм проводит сравнение, противник выбирает ответ, который устранит наименьшее возможное перестановку.

В целом, из -за того, что с элементами $ n $ есть возможные перестановки $ $! !)) = Omega (n log n) $ (при приближении Стерлинга). Для сортировки вставки противник может создать конкретный вход, который приводит к тому, что соответствующее дерево решений имеет глубину как минимум $ omega (n^2) $.

Алгоритм использует массив $ a [1 .. n] $ для хранения входных элементов и основан на следующем инварианте:

В начале каждой итерации FOR LOOP Subarray $ A [1 .. J-1] $ состоит из элементов, первоначально в $ A [1 .. J-1] $, но в отсортированном порядке.

В каждой итерации элементы в $ a [1 .. J-1] $, следовательно, уже находятся в сортированном порядке, и в алгоритме рассматриваются $ a [j] $ и вставляют его в свое окончательное место, сравнивая стоимость $ A $ A [j] $ больше не самая лучшая в сравнении. Элементы в $ a [j+1 .. n] $ находятся в неизвестном состоянии (в отношении порядка сортировки) и будут обрабатываться в более поздних итерациях.

Вот стратегия противника. Зная, что алгоритм работает, вставив $ a [j] $ на свое место, перемещая элементы в $ a [1 .. j-1] $, тогда очевидная стратегия-максимизировать в $ j $ -кую итерацию Количество элементов, которые должны быть перемещены, чтобы разместить $ a [j] $. Это легко выполнить путем тщательного выбора ввода, так что он задний ход отсортировано. Действительно, в этом случае количество элемента, которое должно быть перемещено в каждой итерации, составляет $ J-1 $. Это приводит к тому, что $ Omega (n^2) $ худшее время работы (определяется соответствующей арифметической серией).