Geek asks and answers

Comparing All Array Elements - Algorithm C

I have a m * n matrix, and for each row I need to compare all the elements among them. For each pair that I find, I will call a function that will 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 the following:

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 the algorithm with less complexity.

+5
source share
3 answers

No, this is O (n ^ 2) by definition [too long to explain here, but believe me (-:]
But you can reduce 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)
        }
    }
}
+4
source

, , .

+2

, , , . , , , , , .

, AO (N ^ a) BO (N ^ b) b > a ( ), - N, B A.

:

  • , :

    (arg1, arg2) {   int = index (arg1, arg2);// ,                              // - arg1 * (MAX_ARG2 + 1) + arg2;   if (! stored [i]) {//                              // - ,                              // .        [i] = 1;        [i] = true_function (arg1, arg2);   }    [i]; }

    , . O (| arg1 | * | arg2 |), (, true_function() ) .

    • ( ) :

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

    O (max (M, N)), G [] H []. O (M + N). , F J . :

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

    O (N ^ 2) O (N).

    • , G() H() ( , ).

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

+2
source

More articles:


All Articles