java - 这个算法是O(n^2)吗？

Question

我被设置了一个挑战，并被告知要在 O(n^3) 内解决它，因为显然在 O(n^2) 内这是不可能的，O(n^2) 是原始任务，但它已更改。挑战是编写一个算法来遍历 n*n 矩阵的每一行，然后将整个矩阵打印为排序数组。矩阵的每一行都已排序。

这是我所拥有的，我认为它是 O(n^2)，但我仍在正确地学习 big-O，所以如果我已经完成了，需要一些确认。它使用插入排序实用方法对数组进行排序。谢谢

public int[] mergeMatrix(int[][] matrix) {
    int length = matrix.length;
    int [] sortedMatrixArray = new int[length * length];
    int loop = 1;
    for (int[] i : matrix) {
        for (int j = 0; j < length; j++) {
            switch (loop) {
                case 1:
                    sortedMatrixArray[j] = i[j];
                    break;
                case 2:
                    sortedMatrixArray[j + 3] = i[j];
                    break;
                case 3:
                    sortedMatrixArray[j + 6] = i[j];
                    break;
            }
        }
        loop++;
    }
    insertionSort(sortedMatrixArray);
    return sortedMatrixArray;
}

private void insertionSort(int[] array) {
    for (int firstUnsortedIndex = 0; firstUnsortedIndex < array.length; firstUnsortedIndex++) {
        int newElement = array[firstUnsortedIndex];
        int i;
        for (i = firstUnsortedIndex; i > 0 && array[i-1] > newElement; i--) {
            array[i] = array[i-1];
        }
        array[i] = newElement;
    }
}

编辑:

public int[] mergeMatrix(int[][] matrix) {
    int length = matrix.length;
    int [] sortedMatrixArray = new int[length * length];
    int loop = 0;
    for (int[] i : matrix) {
        for (int j = 0; j < length; j++) {
            if (loop == 0) {
                sortedMatrixArray[j] = i[j];
            }
            sortedMatrixArray[j + (length*loop)] = i[j];
        }
        loop++;
    }
    insertionSort(sortedMatrixArray);
    return sortedMatrixArray;
}

Answer 1

如果n是矩阵的大小，则矩阵有n^2个元素。

您的insertionSort将n^2元素作为输入。它的工作原理是O(k^2)(其中k是输入的大小)，所以总共有O(n^2^2)这是O(n^4)。

要使其O(n^3)，您可以执行以下操作

public class App {
    public static void main(String[] args) {
        int[] result = sort(new int[][]{{1, 4, 7}, {2, 5, 8}, {3, 6, 9}});

        System.out.println("result = " + Arrays.toString(result));
    }

    static int[] sort(int[][] matrix) {
        int total = 0;
        for (int i = 0; i < matrix.length; i++) {
            total += matrix[i].length;
        }

        // indexes variable store current position for each row.
        int[] indexes = new int[matrix.length];
        int[] result = new int[total];
        for (int i = 0; i < total; i++) {
            int minIndex = 0;
            int minValue = Integer.MAX_VALUE;
            // this loop search for row with minimal current position.
            for (int j = 0; j < matrix.length; j++) {
                //Ignore row which are exhausted
                if (indexes[j] >= matrix[j].length) {
                    continue;
                }
                if (matrix[j][indexes[j]] <= minValue) {
                    minIndex = j;
                    minValue = matrix[j][indexes[j]];
                }
            }
            result[i] = matrix[minIndex][indexes[minIndex]];
            indexes[minIndex]++;
        }

        return result;
    }
}

使用一些高级数据结构可以将该算法从 O(n^3) 改进为 O(n^2*log(n))具有最小当前元素的行更快(某种树)。