Number of co-occurrences in a matrix

Question

Number of co-occurrences in a matrix

Navigation

#1 by (2 votes)

0

I have a more mathematical rather than a computational doubt. We assume that we have a square matrix M of dimension n² , where n is any integer greater than zero. By traversing this array, assigning j as row index and i to column indexes, what is the complexity of the algorithm if I consider ij only when i>j ? Below the algorithm demonstration:

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

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

* I know it's a pretty stupid question, but I completely forgot how to find it.

algoritmo

asked by anonymous 03.08.2018 / 02:02

1 answer

Express and Express Generator How to format a Grid inside the Div?

score 2 · Accepted Answer

Your if is already designed to run only on a part of the domain array.

Consider that your domain consists of the following array:

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 elements in d are the elements of the main diagonal, the elements in i are the elements of the lower portion of the main diagonal, and the elements in s are the elements of the upper portion of the main diagonal

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

Regardless of the utility of if , he was asked how many times he would be evaluated. Now, if it covers exactly the elements in i , just count how many houses have i . In the first column m, i has zero elements, then has 1, 2, until in n -th and last column it has n-1 elements.

So it is summed up as follows:

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

What gives n*(n-1)/2 . If you are using some programming language that does integer division, then be careful to ensure that multiplication is done before splitting. Why this care? Because (n-1) is not even, as maybe n is not even, but certainly n*(n-1) is even.