CODEWITHSUNDEEP
pythonalgorithmtime-complexitygraph-theoryconnected-components
Avanish Tiwari
Avanish Tiwari

Reputation: 201

Calculate complexity of algorithm and approach

I have written a code to count group of 1's in binary matrix. Referring to my question link here

code

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)

Can someone please help me to calculate the complexity of this algorithm and what kind of approach it is? Also is there any better approach than this?

As per me complexity and approach(please correct me if I'm wrong):

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

I'm still learning please try to explain me if possible.

Upvotes: 0

Views: 119

Answers (1)

Stef
Stef

Reputation: 15505

The problem you are trying to solve is called counting the connected-components of a graph.

However, which graph are we talking about? Is it:

  • the grid, where each cell of the square matrix is a node in the graph, adjacent to the adjacent cells;
  • the graph whose adjacency matrix is this square matrix?

Consider for instance the following matrix:

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

Your algorithm counts 5 groups in this matrix. This is expected because there are visually five groups in the grid:

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

However, this matrix is the adjacency matrix of the following graph:

0 - 1
|
3   2

Which, as you can see, only has two groups {0, 1, 3} and {2}.

How to fix it

As far as I can see, your algorithm works perfectly to count the number of connected components in the grid. But that is not what you are interested in. You are interested in the number of connected components in the graph represented by this adjacency matrix. You can keep your functions groupcheck and countGroup, whose logic is good, but you should modify them so that a node of the graph is given by just one index i rather than by a pair of indices (i,j); and so that two nodes i and j are considered adjacent by groupcheck if there is a 1 in matrix[i][j].

Your function groupcheck currently "erases" cells which have already be counted by setting their value to 0 with the line matrix[i][j] = 0.

I suggest replacing this by maintaining a set of unseen nodes.

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

Complexity analysis: the complexity of countGroup is n times the complexity of groupcheck. Unfortunately, groupcheck can make up to n recursive calls, and each recursive call contains a for-loop, so the complexity of groupcheck is O(n^2).

Upvotes: 1

Related Questions