доказать, что алгоритм O (n) существует для 10 перестановок

Question

Известной проблемой является поиск минимального количества свопов для сортировки массива. Моя проблема в том, что у нас есть массив размером n, и мы знаем, что можем отсортировать его с 10 перестановками (мы не знаем ходов, только количество ходов). Я хочу доказать, что существует алгоритм O (n) (для времени), который сортирует этот массив.

Прежде всего, для доказательства этого утверждения я должен представить некоторый код? Я не знаю, как это доказать И, во-вторых, это связано с минимальным количеством свопов для сортировки массива?

Спасибо за помощь

Answer 1

Ваше решение в Адаптивных алгоритмах сортировки .

Классическим примером алгоритма адаптивной сортировки является Straight Insertion Sort . В этом алгоритме сортировки мы сканируем ввод слева направо, повторно находя позицию текущего элемента, и вставляем его в массив ранее отсортированных элементов.

Мы знаем, что:

Производительность этого алгоритма может быть описана в терминах количества инверсий на входе, и тогда T(n) будет примерно равен I(A)+(n-1), где I(A) - количество инверсий.

Итак, так как в вашем случае число инверсий постоянно, сложность этого алгоритма будет Theta(n).

Answer 2

Если мы знаем, что 10 сортировок достаточно для сортировки массива, то этот массив почти сортируется с максимумом 10 * 2 = 20 элементов не по порядку. Поэтому, если мы найдем какой-либо алгоритм сортировки, который имеет O (n) для почти отсортированных массивов, то этого достаточно для доказательства вашего утверждения.

Например, мы можем использовать двухшаговое решение:

1. найти все неупорядоченные элементы в массиве, удалить и сохранить их

2. вставить сохраненные элементы в результирующий массив в правильные позиции

СВ таком «наивном» алгоритме в худшем случае потребуется один проход для первого шага и 20 или менее проходов (20 элементов с неупорядоченным порядком) для второго шага. Так что если n >> 10, то он получает O (n) для вашего случая. Это доказательство верно для любого постоянного числа свопов, если оно не зависит от n