Comparaison de tous les éléments du tableau – algorithme C

J’ai une masortingce m * n et, pour chaque ligne, je dois comparer tous les éléments entre eux. Pour chaque couple que je trouve, j’appellerai une fonction qui effectuera des calculs.

Exemple:

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 

Utilisation de CI a écrit ceci:

 for (i=0; i<array_length; i++) { for (k=0; k<array_length; k++) { if (i==k) continue; //Do something } } } 

Je me demandais si je pouvais utiliser un algorithme moins complexe.

Non, c’est O (n ^ 2) par définition [trop long pour expliquer ici, mais croyez-moi (-:]
Mais vous pouvez réduire le nombre d’itérations de moitié:

 for (i=0; i 

Il y a plusieurs choses que vous pourriez faire, mais qui sont possibles et qui ne dépendent pas de la nature du tableau et de la formule que vous appliquez. La complexité globale restra probablement inchangée, voire augmentera, même si le calcul peut être accéléré, à moins que la formule ne dépende de la complexité de ses arguments, auquel cas une réduction de la complexité peut être possible.

De même, aller de AO (N ^ a) à BO (N ^ b) avec b> a (complexité plus élevée) peut encore valoir la peine d’être poursuivi, pour certaines valeurs de N, si B est suffisamment plus petit que A.

Dans aucun ordre particulier:

  • si la masortingce comporte plusieurs éléments répétés, il peut être pratique d’utiliser une fonction de mise en cache:

    fonction de résultat (arg1, arg2) {int i = index (arg1, arg2); // En fonction des valeurs, cela pourrait être // quelque chose comme arg1 * (MAX_ARG2 + 1) + arg2; if (!stocked [i]) {// stocké et les valeurs sont allouées et initialisées // ailleurs – ou dans cette fonction en utilisant un drapeau // statique. stocké [i] = 1; valeurs [i] = fonction_real (arg1, arg2); } retourne les valeurs [i]; }

    Ensuite, vous avez une surcharge de mémoire proportionnelle au nombre de couples de valeurs différents disponibles. La surcharge de l’appel peut être O (| arg1 | * | arg2 |), mais dans certaines circonstances (par exemple, true_function() est chère), les économies réalisées compenseront true_function() la complexité supplémentaire.

    • découpez la formule en morceaux (non possible pour toutes les formules) et exprimez-la en:

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

    alors, vous pouvez faire un cycle O (max (M, N)) pré-calculant G [] et H []. Cela a également un coût de mémoire O (M + N). Ce n’est pratique que si la différence de dépense informatique entre F et J est significative. Ou vous pourriez faire:

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

    ce qui ramène une partie de la complexité de O (N ^ 2) à O (N).

    • les deux premières techniques sont utilisables en tandem si G () ou H () sont pratiques à mettre en cache (plage d’arguments limitée, fonction coûteuse).

    • trouvez une “loi” pour relier F (a, b) à F (a + c, b + d). Vous pouvez ensuite exécuter l’algorithme de mise en cache de manière beaucoup plus efficace, en réutilisant les mêmes calculs. Cela déplace une certaine complexité de O (N ^ 2) à O (N) ou même à O (log N), de sorte que, même si le coût global est toujours quadratique, il croît beaucoup plus lentement et une limite supérieure pour N devient pratique. Si F est lui-même d’un ordre de complexité supérieur à constant dans (a, b), ceci peut également réduire cet ordre (à titre d’exemple extrême, supposons que F soit itératif dans a et / ou b).

Non, vous ne pouvez obtenir une complexité de calcul inférieure que si vous incluez la connaissance du contenu du tableau et la sémantique de l’opération pour optimiser votre algorithme.