计算算法和方法的复杂度

Question

我写了一个代码来计算二进制矩阵中的 1 组。参考my question link here

代码

def groupcheck(i, j, matrix):
    if 0 <= i < len(matrix) and 0 <= j < len(matrix):
        if matrix[i][j]:
            matrix[i][j] = 0
            for dx, dy in ((-1, 0), (1, 0), (0, -1), (0, 1)):
                groupcheck(i + dx, j + dy, matrix)


def countGroup(matrix):
    count = 0;

    for i in range(len(matrix)):
        for j in range(len(matrix)):
            if matrix[i][j]:
                count += 1
                groupcheck(i, j, matrix)
    return count

matrix = [
    [1,1,0,0],
    [1,1,1,0],
    [0,1,1,0],
    [0,0,0,1] 
]

group = countGroup(matrix)
print(group)

谁能帮我计算一下这个算法的复杂度，它是一种什么样的方法？还有比这更好的方法吗？

根据我的复杂度和方法（如有错误请指正）：

complexity : O(n^2*4) (n is length of square matrix)
approach: brute force

我还在学习中，请尽可能解释一下。

Answer 1

您要解决的问题称为计算图的connected-components。

但是，我们在谈论哪个图表？是：

网格，其中方阵的每个单元格是图中的一个节点，与相邻的单元格相邻；
邻接矩阵是这个方阵的图？

例如考虑以下矩阵：

[[1,1,0,1],
 [1,1,0,0],
 [0,0,1,0],
 [1,0,0,1]]

您的算法计算此矩阵中的 5 个组。这是预期的，因为在网格中视觉上有五个组：

[[A,A,0,B],
 [A,A,0,0],
 [0,0,C,0],
 [D,0,0,E]]

然而，这个矩阵是下图的邻接矩阵：

0 - 1
|
3   2

如您所见，只有两个组 {0, 1, 3} 和 {2}。

如何修复

据我所知，您的算法非常适合计算网格中连通分量的数量。但这不是您感兴趣的。您感兴趣的是此邻接矩阵表示的图中连通分量的数量。你可以保留你的函数 groupcheck 和 countGroup，它们的逻辑是好的，但是你应该修改它们以便图的节点只由一个索引 i 而不是一对给出指数 (i,j)；因此，如果 matrix[i][j].

中有 1，则 groupcheck 认为两个节点 i 和 j 相邻

您的函数 groupcheck 当前“擦除”已经通过使用行 matrix[i][j] = 0.

将它们的值设置为 0 进行计数的单元格

我建议通过维护一组看不见的节点来替换它。

def groupcheck(i, matrix, unseen):
  for j in range(len(matrix)):
    if (j in unseen) and matrix[i][j]:  # if i and j are adjacent
      unseen.discard(j)
      groupcheck(j, matrix, unseen)

def countGroup(matrix):
  count = 0
  unseen = set(range(len(matrix)))
  while unseen:
    i = unseen.pop()
    count += 1
    groupcheck(i, matrix, unseen)
  return count

复杂度分析：countGroup的复杂度是groupcheck的n倍。不幸的是，groupcheck最多可以进行n次递归调用，而每次递归调用都包含一个for循环，所以groupcheck的复杂度是O(n^2)。

计算算法和方法的复杂度

Calculate complexity of algorithm and approach

python

algorithm

graph-theory

time-complexity

connected-components

如何修复