时间戳

首页 > 解决方案 > 正确的时间复杂度是多少？

java - 正确的时间复杂度是多少？

问题描述

我正在编写一个算法来将* n 矩阵转换为单个数组。

1 2 3

4 5 6

7 8 9

= [1, 2, 3, 4, 5, 6, 7, 8, 9]

如果我所做的是 O(n 2 ) 或 O(n 3 )，我会感到困惑：

public int[] mergeMatrix(int[][] matrix) {
    List<Integer> tempList = new ArrayList<>();
    for (int[] array : matrix) {
        for (int i : array) {
            tempList.add(i);
        }
    }
    int totalLength = tempList.size();
    int[] mergedArray = new int[totalLength];
    for (int i = 0; i < tempList.size(); i++) {
        mergedArray[i] = tempList.get(i);
    }
    return mergedArray;
}

会是 O(n 2 )，因为这是算法过程中最长的最坏情况，还是 O(n 3 )，因为 O(n) + O(n 2 ) = O(n 3 )？

标签： javaarraysbig-o

解决方案

其运行时复杂度为 O(nm)，其中n是行数，m是矩阵中的列数。

这样做的原因：

  • 您对矩阵总数中的每个元素只执行一次操作，这取决于您拥有的行数和列数。

在 的上下文中n = m，这将是 O(n*n) 或 O(n 2 )，但仅此而已。

循环的数量在这里并不重要，因为你可以用它进行令人难以置信的花哨的迭代。请务必查看您在循环中实际执行的操作；因为它们是线性的，我希望运行时是线性运行时乘以线性运行时，因为嵌套的性质。

推荐阅读