2^N数组插入排序的时间复杂度？

Question

考虑一个整数数组，其大小为2^N，其中索引X处的元素（0≤X < 2N）为X xor 3（即X的两个最低有效位被翻转）。这个数组插入排序的运行时间是多少？

Answer 1

检查的列表的样子的结构：

对于n = 2：

{3，2，1，0}

对于n = 3：

{ 3，2，1，0，7，6，5，4}

对于插入排序，您保持从1到当前索引的列表排序的不变量，所以您在任务步骤是放置c urrent元素放入它之前的已排序元素中的正确位置。在最糟糕的情况下，您必须遍历所有以前的索引，然后才能插入当前值（想想列表按逆序排序的情况）。但从上面的结构可以清楚地看出，对于具有属性的列表，每个值与索引^ 3相当，列表中距离任何给定索引最远的返回值为3，所以你减少了你必须在插入步骤中将O（n）工作到一个常数因子的可能性。但是你仍然需要做O（n）工作来检查列表中的每个元素。因此，对于这种特殊情况，插入排序的运行时间在输入大小上是线性的，而在最坏的情况下，它是二次的。