K-移位数组插入排序的时间复杂度

Question

这个问题是在我的算法课程作业中提出的。

--一开始有n个大小的排序数组。假设是n=10，数组是[1,2,3,4,5,6,7,8,9,10]。然后它被循环地移到了k的右边，假设是k=3。现在数组是[8,9,10,1,2,3,4,5,6,7]。

如果根据n和k对此数组应用插入排序，那么时间复杂度是多少？

我对这个问题做了很多研究，但在网上找不到解决办法。如何确定这种移位数组插入排序的时间复杂度？

Answer 1

首先，插入排序：

static void insertionSort(int[] array) {
    for (int i = 1; i < array.length; i++) {
        int key = array[i];
        int j = i - 1;

        while (j >= 0 && array[j] > key) {
            array[j + 1] = array[j];
            j--;           
        }

        array[j + 1] = key;
    }
}

时间复杂性主要取决于以下几行，因为比较和交换操作就是在这里完成的。

while (j >= 0 && array[j] > key) {
    array[j + 1] = array[j];
    j--;
}

取一张纸，为每个j值绘制一个交换表。

​

​

最后，您将了解到，该算法进入does循环(n-k)时间，每当它进入时，它就会交换操作k时间。因此，时间复杂性是(n-k)*k。

我们来证明一下。

在算法中放置一个交换计数器变量。

static int insertionSort(int[] array) {
    int swapCount = 0;

    for (int i = 1; i < array.length; i++) {
        int key = array[i];
        int j = i - 1;
        while (j >= 0 && array[j] > key) {
            array[j + 1] = array[j];
            j--;
            swapCount++;
        }

        array[j + 1] = key;
    }

    return swapCount;
}

现在，让我们在问题中描述的数组上尝试一下。

public class App {
    public static void main(String[] args) throws Exception {
        int[] baseArray = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };

        int n = baseArray.length;
        int k = 3;

        // Shift base array by k
        int[] shiftedArray = shiftArray(baseArray, k);

        // Calculate how many swaps done by the insertion sort
        int swapCount = InsertionSort.insertionSort(shiftedArray);

        // Theroitical value is calculated by using the formula (n-k)*k
        int timeComplexityTheoritical = (n - k) * k;

        System.out.print("Theoritical Time Complexity based on formula: " + timeComplexityTheoritical);

        System.out.print(" - Swap Count: " + swapCount);

        System.out.print(" - Is formula correct:" + (timeComplexityTheoritical == swapCount) + "\n");
    }

    // Shift array to the right circularly by k positions
    static int[] shiftArray(int[] array, int k) {
        int[] resultArray = array.clone();

        int temp, previous;
        for (int i = 0; i < k; i++) {
            previous = resultArray[array.length - 1];
            for (int j = 0; j < resultArray.length; j++) {
                temp = resultArray[j];
                resultArray[j] = previous;
                previous = temp;
            }
        }

        return resultArray;
    }

    static class InsertionSort {

        static int insertionSort(int[] array) {
            int swapCount = 0;

            for (int i = 1; i < array.length; i++) {
                int key = array[i];
                int j = i - 1;
                while (j >= 0 && array[j] > key) {
                    array[j + 1] = array[j];
                    j--;
                    swapCount++;
                }

                array[j + 1] = key;
            }

            return swapCount;
        }
    }
}

产出：

基于公式的

理论时间复杂度: 21 -交换计数: 21 -公式正确:真

我在大小为2^16的数组上试过，每次公式都是正确的，并将其移动2^16-1次。

我们发现的时间复杂度不是上界或下界，而是这种情况的精确紧界。所以它就是Theta。Θ((n-k)k)。