最大排列数

Question

一些排序算法，如插入排序，对于n的某个子集具有Θ（n）渐近运行时！ n个元素的可能排列，这意味着对于那些排列，插入排序所做的比较的数量是针对某个常数k的kn。对于给定的常数k，任何给定的比较排序可以在kn比较中终止的最大排列数是多少？

Answer 1

插入排序中的操作数取决于反转次数。所以我们需要评估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

Answer 2

每次比较最多可以将您可以区分的输入排列从不加倍。因此，通过kn比较，您可以排序最多2^(kn)排列。