Complexité accidentelle

En développement logiciel le terme complexité accidentelle désigne la complexité introduite dans des programmes informatiques non en raison de la complexité du problème, mais de manière accidentelle en raison de choix de développement non pertinents. Il a été inventé par Frederick Brooks dans son article No Silver Bullet ^[1]. Ce terme est réutilisé dans différentes études proposant des outils pour lutter contre ce phénomène ^[2]^,^[3].

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.

Solution

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 la complexité accidentelle.

Exemple

Afin d'illustrer cet anti-patron, nous allons essayer de répondre au problème de la somme des $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 à $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 $O(n)$ . Comme attendu, il existe une solution algorithmique répondant à ce problème en une complexité temporelle restreinte ( $O(1)$ ) :

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

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

Complexité accidentelle

Solution

Exemple

Articles connexes

Notes et références

Related Articles