Максимальное количество перестановок

Question

Некоторые алгоритмы сортировки, такие как сортировка вставкой, имеют асимптотическое время выполнения Θ (n) для некоторого подмножества n!возможные перестановки из n элементов, что означает, что для этих перестановок число сравнений, которые выполняет сортировка вставкой, равно kn для некоторой константы k.Для данной константы k, каково максимальное число перестановок, для которых любой данный вид сравнения может завершиться в пределах сравнений kn?

Answer 1

Каждое сравнение максимально удваивает количество входных перестановок, которые вы можете различить.Таким образом, с kn сравнениями вы можете сортировать не более 2^(kn) перестановок.

Answer 2

Количество операций в сортировке вставки зависит от количества инверсий.Поэтому нам нужно оценить количество перестановок n значений (1..n для простоты), содержащих ровно k инверсий.

Мы видим, что Inv(n, 0) = 1 - отсортированный массив
Также Inv(0, k) = 0 - пустой массив

Мы можем получить массив с n элементами и k инверсиями:
-добавление значения n в конец массива с n-1 элементами и k инверсиями (таким образом, число инверсий остается неизменным) - вставка значения n до конца массива с n-1 элементами и k-1 инверсиями (таким образом, добавление одной инверсии)
- вставка значения n перед двумя элементами в концемассива с n-1 элементами и k-2 инверсиями (с добавлением двух инверсий)
- и так далее

Используя этот подход, мы можем просто заполнить таблицу Inv[n][k] строка за строкой иячейка за ячейкой

  Inv[n][k] = Sum(Inv[n-1][i]) where j=0..k