2 ^ N数组的插入排序的时间复杂性? [英] Time complexity with insertion sort for 2^N array?

问题描述

考虑一个整数数组，该数组的大小为2 ^ N，其中索引X(0≤X <2N)处的元素为X x或3(即X的两个最低有效位被翻转).该数组上的插入排序的运行时间是多少?

Consider an array of integers, which has a size of 2^N, where the element at index X (0 ≤ X < 2N) is X xor 3 (that is, two least significant bits of X are flipped). What is the running time of the insertion sort on this array?

推荐答案

检查列表的结构:

对于n = 2:

{3，2，1，0}

{3, 2, 1, 0}

对于n = 3:

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

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

对于插入排序，您要保持不变，即对从1到当前索引的列表进行排序，因此每一步的任务是将当前元素放置在排序元素之前的正确位置.在最坏的情况下，必须先遍历所有先前的索引，然后才能插入当前值(请考虑将列表按相反的顺序排列的情况).但是从上面的结构可以清楚地看到，对于一个具有该属性的列表，每个值都等于索引^ 3，那么您必须从任何给定索引中返回的列表中最远的位置是3.因此，您已经减少了您必须在插入步骤中将O(n)的工作设为恒定因子的可能性.但是您仍然必须执行O(n)工作来检查列表中的每个元素.因此，对于这种特殊情况，插入排序的运行时间在输入的大小上是线性的，而在最坏的情况下，它是二次的.

For insertion sort, you're maintaining the invariant that the list from 1 up to your current index is sorted, so you're task at each step is to place the current element into it's correct place among the sorted elements before it. In the worst case, you will have to traverse all previous indices before you can insert the current value (think of the case where the list is in reverse sorted order). But it's clear from the structure above that for a list with the property that each value is equivalent to the index ^ 3, that the furthest back in the list that you would have to go from any given index is 3. So you've reduced the possibility that you'd have to do O(n) work at the insertion step to a constant factor. But you still have to do O(n) work to examine each element of the list. So, for this particular case, the running time of insertion sort is linear in the size of the input, whereas in the worst case it is quadratic.

这篇关于2 ^ N数组的插入排序的时间复杂性?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！