Number of co-occurrences in a matrix

Asked

Viewed 42 times

0

I have a question more mathematical than computational. Suppose we have a square matrix M of dimension n², where n is any integer greater than zero. Traversing this matrix, assigning j as an index of lines and i to column indexes, what is the complexity of the algorithm if I consider ij only when i>j? Below the demonstration of the algorithm:

for i=0; i<n-1; i++:
  for j=i+1; i<n; j++:
    if i>j:
      ////cont..

I want to know what function to determine, from n, how many times the if will be checked. In other words, how many elements are in the triangular matrix below the diagonal.

*I know it’s a really dumb question, but I completely forgot how to find that function.

algorithm

  • (n-1)**2/2, or something very close, I would say.

  • By the way, I think there’s something strange about it. In your code, you change the value of i in intent iteration. With this, you will only execute x steps and will fall out of the two loops. Not to mention you get to talk about n and enter in the code x, that is out of context

  • It is! Some errors in the algorithm, now that I’ve seen, but it’s just an example of the problem, the x is the same as n and the second time is j<x and j++ and not i

1 answer

2


Your if has already been designed for it to run only on a part of the domain matrix.

Consider that your domain consists of the following matrix:

d s s s s
i d s s s
i i d s s
i i i d s
i i i i d

Where the elements in d are the main diagonal elements, the i are the elements of the lower portion than the main diagonal and the elements in s are the elements of the upper portion of the main diagonal.

Its iteration perfectly covers only the elements in i, without lack. Therefore, whatever the purpose of the if (which apparently ensures that the element is necessarily in s, whereas the outer loop is column change and the inner, row), it has become useless due to how the loop was drawn.

Regardless of the utility of if, was questioned as to how many times he would be evaluated. Now, whether he covers exactly the elements in i, just count how many houses you have i. In the first column m, i has zero elements, then has 1, 2, until no n-eleventh and last column he has n-1 elements.

Therefore, it is the following summation:

Área(i) = 1 + 2 + ... + (n - 1)

That gives n*(n-1)/2. If you are using some programming language that does entire division, then be careful to ensure that multiplication is done before division. Why this caution? Because maybe (n-1) not even, just like maybe n not either, but certainly n*(n-1) is par.

  • That’s the function I really wanted to find n*(n-1)/2. The closest I had come was (n²÷2)−log2(n), but the value is not always integer and as we know, the lower triangular matrix will always have a number of elements (i) integer.

  • @Francisconephew n/2 ~~= log2(n) for small values. Do not forget, being right the answer, to mark it as accepted on so that other people can take advantage of the knowledge also

Browser other questions tagged algorithm

You are not signed in. Login or sign up in order to post.