计算算法和方法的复杂度

2024-05-20 • 问答

我写了一个代码来对二进制矩阵中的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,-1),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,matrix)
    return count

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

group = countGroup(matrix)
print(group)

有人可以帮助我计算该算法的复杂度以及它是哪种方法吗？还有没有比这更好的方法了？

根据我的复杂性和方法（如果我错了，请纠正我）：

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

我还在学习，请尝试向我解释。

您要解决的问题称为计算图形的连通分量。

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

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

例如考虑以下矩阵：

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

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

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

但是，此矩阵是下图的邻接矩阵：

0 - 1
|
3   2

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

如何修复

据我所知，您的算法非常适合计算网格中连接的组件的数量。但这不是您感兴趣的。您对由该邻接矩阵表示的图中的连接组件的数量感兴趣。您可以保留逻辑groupcheck和countGroup的功能，但是您应该对其进行修改，以使图的节点仅由一个索引i而不是一对索引给出索引(i,j)中；并且如果i中有1，则两个节点j和groupcheck被matrix[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,unseen)

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

复杂度分析：countGroup的复杂度是n的复杂度groupcheck的两倍。不幸的是，groupcheck最多可以构成n个递归调用，并且每个递归调用都包含一个for循环，因此groupcheck的复杂度为O(n^2)。 / p>

计算算法和方法的复杂度

linjianshe12 回答：计算算法和方法的复杂度

如何修复

大家都在问