Comparison of all array elements - C algorithm

Question

I have a matrix m * n and, for each row, I need to compare all elements among them. For each couple I find, I'll call a function that is going to perform some calculations.

Example:

my_array -> {1, 2, 3, 4, 5, ...}

I take 1 and I have: (1,2)(1,3)(1,4)(1,5)
I take 2 and I have: (2,1)(2,3)(2,4)(2,5)
and so on

Using C I wrote this:

for (i=0; i<array_length; i++) {
    for (k=0; k<array_length; k++) {
        if (i==k) continue;

           //Do something
        }
    }
}

I was wondering if I can use an algorithm with lower complexity.

Answer 1

No, it's O(n^2) by definition [ too long to explain here, but trust me (-: ]
But you can decrease the number of iterations by half :

for (i=0; i<array_length; i++) {
    for (k=i+1; k<array_length; k++) { // <-- no need to check the values before "i"
           //Do something
           //If the order of i and k make a different then here you should:
           //'Do something' for (i,k) and 'Do something' for (k,i)
        }
    }
}

Answer 2

There are several things you might do, but which are possibile and which not depend on the array nature and the formula you apply. Overall complexity will probably remain unchanged or even grow, even if calculation can be made to go faster, unless the formula has a complexity dependancy on its arguments, in which case a decrease in complexity may be achievable.

Also, going from AO(N^a) to BO(N^b) with b > a (higher complexity) can still be worth pursuing, for some range of N, if B is sufficiently smaller than A.

In no particular order:

• if the matrix has several repeated items, it can be convenient to use a caching function:

  result function(arg1, arg2) { int i = index(arg1, arg2); // Depending on the values, it could be // something like arg1*(MAX_ARG2+1) + arg2; if (!stored[i]) { // stored and values are allocated and initialised // somewhere else - or in this function using a // static flag. stored[i] = 1; values[i] = true_function(arg1, arg2); } return values[i]; }

  Then, you have a memory overhead proportional to the number of different couples of values available. The call overhead can be O(|arg1|*|arg2|), but in some circumstances (e.g. true_function() is expensive) the savings will more than offset the added complexity.

  • chop the formula into pieces (not possible for every formula) and express it as:

    F(x,y) = G(x) op H(y) op J(x,y)

  then, you can do a O(max(M,N)) cycle pre-calculating G[] and H[]. This also has a O(M+N) memory cost. It is only convenient if the computational expenditure difference between F and J is significant. Or you might do:

  for (i in 0..N) {
      g = G(array[i]);
      for (j in 0..N) {
          if (i != j) {
              result = f(array[i], array[j], g);
          }
      }
  }
  

  which brings some of the complexity from O(N^2) down to O(N).

  • the first two techniques are useable in tandem if G() or H() are practical to cache (limited range of argument, expensive function).

  • find a "law" to link F(a, b) with F(a+c, b+d). Then you can run the caching algorithm much more efficiently, reusing the same calculations. This shifts some complexity from O(N^2) to O(N) or even O(log N), so that while the overall cost is still quadratic, it grows much more slowly, and a higher bound for N becomes practical. If F is itself of a higher order of complexity than constant in (a,b), this may also reduce this order (as an extreme example, suppose F is iterative in a and/or b).

Answer 3

No, you can only get lower computational complexity if you include knowledge of the contents of the array, and semantics of the operation to optimize your algorithm.