Complexité accidentelle

Le terme de complexité accidentelle est lié au problème créé par une implantation ou un langage donné. Ce terme s'oppose à celui de complexité essentielle qui lui décrit la complexité propre à un problème.

Les causes sont diverses :

• le développeur n'est pas familier avec les capacités de la technologie utilisée ;
• le souhait de généraliser le travail en prévision de fonctionnalités futures ;
• le développeur ne prend pas le temps d'optimiser et de réusiner son code : il en résulte une complexité croissante.

Les solutions pour contrer ces causes sont :

• prendre le temps de se former aux technologies afin d'appréhender plus finement leurs possibilités ;
• éviter de généraliser les fonctionnalités et ainsi tout surcoût en complexité ;
• prendre soin de réusiner son code.

Dans un monde utopique, il existerait un programme capable de simplifier n'importe quel code afin d'en éliminer sa complexité accidentelle.

Afin d'illustrer cet anti-patron, nous allons essayer de répondre au problème de la somme des ${\displaystyle n}$ premiers nombres impairs.

Dans une première implantation du problème, nous utilisons une variable somme_impairs comme compteur sommant les nombres impairs et impair_suivant pour déterminer le prochain nombre impair à sommer. Il s'ensuit une boucle allant de 0 à ${\displaystyle n}$ (exclu) permettant de sommer la suite des n premiers impairs :

unsigned int somme_n_impairs(unsigned int n) {
	unsigned int somme_impairs = 0;
	unsigned int impair_suivant = 1;
	for (int i = 0; i < n; n++) {
		somme_impairs = somme_impairs + impair_suivant;
		impair_suivant = impair_suivant + 2
	}
	return somme_impairs;
}

Cet algorithme possède une complexité temporelle en ${\displaystyle O(n)}$. Comment attendue, il existe une solution algorithmique répondant à ce problème en une complexité temporelle restreinte (${\displaystyle O(1)}$) :

unsigned int somme_n_impairs(unsigned int n) {
	return n * n;
}

La somme des ${\displaystyle n}$ premiers nombres impairs est ${\displaystyle 1+3+5+...+(2n-1)=n^{2}}$. Animation 3D de deux vues sur un tétraèdre.

Pour répondre à ce problème, il suffit de monter au carré le paramètre ${\displaystyle n}$ : ${\displaystyle S_{n}=1+3+5+\cdots +(2n-1)=\sum _{i=1}^{n}(2i-1)=n^{2}}$.

• Complexité essentielle
• Pas de balle en argent
• Anti-patron
• Patron de conception