этот алгоритм 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;
    }
}

EDIT:

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)) с использованием некоторой продвинутой структуры данных, которая позволяет быстрее находить строки с минимальным текущим элементом (своего рода дерево).

Answer 2

Вы правы, это O (n ^ 2). Ваша вставкаSort также O (n ^ 2), но, так как вы вызываете ее после завершения первых 2 циклов for, время выполнения O (N ^ 2) + О (п ^ 2) = O (N ^ 2)