我如何找到时间复杂度?

huangapple go评论72阅读模式
英文:

How can I find the time complexity?

问题

The correct time complexity for the given code is O(n^2), where "n" represents the number of rows or columns, which is 6 in this case. The code contains two nested loops iterating over the rows and columns of a 6x6 grid, resulting in a time complexity of O(n^2) due to the nested structure.

英文:

The main is to get a 6*6grid from user. The input will be stored in a 2d array. Is the time complexity should be O(n^2)? Since, I have a nested loop. But the code operates in a fixed 6 rows and 6 cols that are static. Or the time complexity should be O(n)? as the number of row and column are constant and set equals to 6.

public class MatrixGrid {
    private static char[][] grid = new char[6][6];
    private static int rows = 6;
    private static int cols = 6;

    public static void main(String[] args) {
        MatrixGrid matrixGrid = new MatrixGrid ();
        matrixGrid.getGridFromUser();  //get user input
        int totalHomeAreas = 0;
        int maxHomeAreaSize = 0;

        for (int i = 0; i < rows; i++) {  //---n
            for (int j = 0; j < cols; j++) {  //--n
                if (grid[i][j] == 'H') {
                    int currentSize = matrixGrid.dfs(i, j);
                    totalAreas++;
                    maxAreaSize= Math.max(maxAreaSize, currentSize );
                }
            }
        }
}

What's the correct time complexity?

答案1

得分: 0

考虑到循环迭代是常数6*6,即使循环是嵌套的。

根据嵌套循环大小i和j的一般规则,复杂度将为O(ij)。由于大小是常数,迭代是有限的,因此复杂度将为O(66),即O(1)。

因此,对于常数迭代,它将始终为O(1)。

如果您的行和列大小变化但相同,那么复杂度将为O(n^2),其中n是行/列的数量。

如果您的行和列大小变化,但不相同,那么复杂度将为O(m*n),其中m是行的数量,n是列的数量。

英文:

Considering the loop iterations are constant 6*6, even though the loop is nested.

By general rule for nested loop of size i and j, the complexity would be O(ij). Now due to constant size the iterations are finite, so the complexity would be O(66), which if O(1).

So resulting for constant iterations, it will be always O(1).

If your row and column size are varying but same, then it would be O(n^2), where n is number of rows/columns.

If your row and column size are varying, but not same, then it would be O(m*n), when m is number of rows and n is number of columns.

答案2

得分: 0

时间复杂度在所有情况下都基于您的代码行int currentSize = matrixGrid.dfs(i, j);。因为没有提到它,我们假设matrixGrid.dfs(i, j)的时间复杂度是O(1)

然后,当我们分配n = size(grid) = rows * cols时,main的时间复杂度是O(n),或者当我们分配n = rows = cols时,时间复杂度为O(n^2);这两个选项都是正确的。

最后,考虑到常数时间复杂度,您应该定义数据约束。如果您将约束定义为rows = 6, cols = 6,那么常数时间复杂度为O(1)。否则,如果约束更像是rows = n, cols = n, 0 <= n <= 10^4,那么时间复杂度是O(n^2),与上面提到的示例类似。

因此,计算时间复杂度的关键是"数据的约束条件"。

英文:

The time complexity in all cases is based on your line int currentSize = matrixGrid.dfs(i, j);. Since there is not metion on it, we assume the time complexity of matrixGrid.dfs(i, j) is O(1).

Then the time complexity of main is O(n) when we assign n = size(grid) = rows * cols, or O(n^2) when we assign n = rows = cols; both options are correct.

Finally, considering the constant time complexity, you should define your data constraints. If you define the constraints as rows = 6, cols = 6, then there is constant time complexity O(1). Otherwise, if the constraints are more like rows = n, cols = n, 0 &lt;= n &lt;= 10^4, then the time complexity is O(n^2), similar to the examples mentioned above.

So, the key to calculating time complexity is "the constraints of the data".

答案3

得分: 0

复杂性不能是关于 n 的函数,因为在您的代码中没有 n

理解 O(n²) 不是一个非正式的表达方式,用来表示时间“增长速度比输入大小快”。它确实是一个依赖于参数的数学表达式。

英文:

The complexity cannot be a function of n for the simple reason that there is no n in your code.

Understand that O(n²) is not a informal expression to say that the time "grows faster than the size of the input". It really is a mathematical expression depending on the argument.

huangapple
  • 本文由 发表于 2023年7月17日 13:01:01
  • 转载请务必保留本文链接:https://go.coder-hub.com/76701605.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定