python - 如何降低以下代码的时间复杂度

Question

谁能解释我如何降低从二维数组中找到最大数量的代码的时间复杂度

mat = [[17, 2, 33, 4],
               [25, 66, 7, 8],
               [9, 10, 78, 12],
               [13, 14, 15, 16]]
    import sys
    max = -sys.maxsize - 1
    N = 4
    M = 4
    
    for i in range(N):
      for j in range(M):
        if (mat[i][j] > max):
          max = mat[i][j]
    
    print(max)

标签： pythonalgorithmoptimizationmultidimensional-arraytime-complexity

Answer 1

您无法降低O-Notation 的复杂性，因为您至少需要读取所有输入。所以没有算法的复杂度可以低于O(N*M)（其中 N，M 是矩阵的维度）