下面给出的代码的时间复杂度是多少？

Question

下面给出的代码中 findMaxArea 函数的时间复杂度是多少？

问题来源： https://practice.geeksforgeeks.org/problems/length-of-largest-region-of-1s-1587115620/1#

class Solution:
    def dfs(self,i,j,grid,row,colm):
        if i<0 or j<0 or i>=row or j>=colm or grid[i][j]!=1:
            return 0
        res=0
        grid[i][j]=2
        res+=self.dfs(i+1,j,grid,row,colm)
        res+=self.dfs(i,j+1,grid,row,colm)
        res+=self.dfs(i+1,j+1,grid,row,colm)
        res+=self.dfs(i-1,j-1,grid,row,colm)
        res+=self.dfs(i-1,j,grid,row,colm)
        res+=self.dfs(i,j-1,grid,row,colm)
        res+=self.dfs(i+1,j-1,grid,row,colm)
        res+=self.dfs(i-1,j+1,grid,row,colm)
        return res+1
        

    #Function to find unit area of the largest region of 1s.
    def findMaxArea(self, grid):
        #Code here
        row=len(grid)
        colm=len(grid[0])
        maximum=-1
        for i in range(row):
            for j in range(colm):
                if grid[i][j]==1:
                    maximum=max(maximum,self.dfs(i,j,grid,row,colm))
        return maximum

#{ 
#  Driver Code Starts


if __name__ == '__main__':
    #T is number of test cases
    T=int(input())
    for i in range(T):
        #size of matrix n x m
        n, m = map(int, input().split())
        grid = []
        for _ in range(n):
            a = list(map(int, input().split()))
            grid.append(a)
        obj = Solution()
        ans = obj.findMaxArea(grid)
        print(ans)

# } Driver Code Ends

Answer 1

你正在对矩阵进行 dfs 以找到 1 的最大面积。

尽管您正在进行递归调用，但在最坏的情况下您只访问每个元素一次，例如当整个矩阵用1填充或者整个矩阵用0填充时。

因此时间复杂度为 O(m*n)，其中 m 是行数，n 是矩阵中的列数。

下面给出的代码的时间复杂度是多少？

What would be the time complexity of the below-given code?

time-complexity

data-structures