Identifier et Évaluer la Complexité d'une Solution Brute-Force

1. Qu'est-ce que l'approche par "force brute" ?

Imaginez que vous avez un énorme trousseau de clés et une seule porte à ouvrir. L'approche la plus simple, sans réfléchir, serait d'essayer chaque clé, une par une, jusqu'à trouver la bonne. C'est exactement l'idée de la force brute en algorithmique.

Une approche par force brute consiste à énumérer systématiquement toutes les solutions possibles à un problème et à vérifier pour chacune si elle est valide. C'est une méthode directe, qui ne demande pas de "ruse" particulière, mais qui garantit de trouver la solution si elle existe.

Pour une définition plus formelle, je vous propose de lire un court extrait d'un document sur la conception d'algorithmes.

Comme vous l'avez lu, la force brute est souvent simple à imaginer, mais son principal inconvénient est son coût : elle peut être extrêmement lente. Voyons cela avec des exemples concrets.

2. Identifier et analyser une solution par force brute

La structure la plus courante d'un algorithme par force brute implique des boucles imbriquées pour générer toutes les combinaisons possibles des éléments d'entrée.

Exemple 1 : La somme de deux nombres (Complexité $O(n^2)$)

Problème : Étant donné un tableau T de n nombres et un nombre cible S, existe-t-il deux nombres dans le tableau dont la somme est égale à S ?

Solution par force brute : Nous allons simplement tester toutes les paires de nombres possibles.

1. Prendre le premier nombre.
2. L'additionner avec tous les autres nombres qui le suivent.
3. Si une somme est égale à S, on a trouvé une solution.
4. Sinon, on passe au deuxième nombre et on recommence le processus.

Voici le pseudo-code correspondant :

Fonction TrouverSomme(T, S)
  n = longueur(T)
  Pour i allant de 0 à n - 2
    Pour j allant de i + 1 à n - 1
      Si T[i] + T[j] == S
        Retourner Vrai
  Retourner Faux

Analyse de la complexité :

• Nous avons deux boucles imbriquées (Pour i... et Pour j...).
• La variable n représente la taille des données d'entrée (le nombre d'éléments dans le tableau T).
• La boucle externe s'exécute environ n fois.
• Pour chaque itération de la boucle externe, la boucle interne s'exécute aussi un nombre de fois qui dépend de n. Dans le pire des cas, c'est aussi de l'ordre de n.
• Le nombre total d'opérations (additions et comparaisons) est donc proportionnel à $n\times n=n^2$.
• La complexité de cet algorithme est quadratique, notée $O(n^2)$.

Exemple 2 : Analyse d'un algorithme naïf (Complexité $O(n^3)$)

Regardons maintenant un exemple avec trois boucles imbriquées. L'image ci-dessous montre un algorithme "naïf" (un autre terme pour force brute) écrit en Python et analyse sa complexité.

Même sans comprendre le problème exact que ce code résout, nous pouvons analyser sa structure :

1. La structure : On voit clairement trois boucles for imbriquées les unes dans les autres : for i in range(...), for j in range(...), et for k in range(...). Chacune de ces boucles parcourt une partie du tableau d'entrée de taille n.
2. Le calcul de la complexité : Comme pour l'exemple précédent, le nombre total d'opérations est en grande partie déterminé par ces boucles. Avec trois boucles imbriquées, le nombre d'opérations sera proportionnel à $n\times n\times n=n^3$. La complexité est donc cubique, notée $O(n^3)$.
3. L'impact réel : La partie la plus intéressante est la table d'exécution. Pour n=1000, le temps est de 2,2 secondes. Mais si on passe à n=10000 (10 fois plus grand), le temps estimé explose à 36 minutes ! Pour n=100000, on parle de 25 jours. Cela illustre parfaitement pourquoi il est crucial d'évaluer la complexité : une solution par force brute peut devenir totalement inutilisable lorsque la taille des données augmente.

3. Quand la complexité explose : le cas factoriel

Les complexités polynomiales comme $O(n^2)$ ou $O(n^3)$ sont déjà coûteuses, mais certains problèmes génèrent par force brute des complexités encore pires.

Rappel sur les classes de complexité

Avant d'aller plus loin, il est bon de se remémorer l'échelle des complexités.

Exemple 3 : Le Problème du Voyageur de Commerce (Complexité $O(n!)$)

C'est l'un des problèmes les plus célèbres en informatique.

Problème : Un vendeur doit visiter un ensemble de villes. Connaissant la distance entre chaque paire de villes, quel est le circuit le plus court qui passe par chaque ville une seule fois et revient à la ville de départ ?

Solution par force brute :

1. Énumérer tous les circuits possibles (toutes les permutations des villes).
2. Pour chaque circuit, calculer sa longueur totale.
3. Garder en mémoire le circuit le plus court trouvé jusqu'à présent.

Le problème est que le nombre de circuits possibles explose très rapidement. Pour n villes, il y a (n-1)! circuits à vérifier (le ! est le symbole de la factorielle : $n!=n\times (n-1)\times ...\times 2\times 1$). La complexité est donc factorielle, notée $O(n!)$.

Le document suivant illustre de manière spectaculaire à quel point cette approche est impraticable.

Ce tableau est sans appel : même avec un ordinateur hypothétique remplissant l'univers et calculant à la vitesse de la lumière, la force brute est vaincue par la "combinatoire" du problème pour un nombre de villes finalement assez modeste.

4. La force brute : une stratégie à ne pas écarter

Après avoir vu ces exemples, on pourrait penser que la force brute est toujours une mauvaise idée. Ce n'est pas le cas ! C'est un outil important dans la boîte à outils d'un développeur. Elle est utile :

• Pour de petites entrées : Si vous savez que n sera toujours très petit, une solution en $O(n^2)$ ou même $O(n^3)$ peut être tout à fait acceptable et plus simple à écrire et à maintenir qu'un algorithme complexe.
• Comme point de départ : C'est souvent la première solution à laquelle on pense. L'implémenter permet de mieux comprendre le problème.
• Pour vérifier une solution optimisée : Lors du développement d'un algorithme plus complexe, on peut utiliser la solution par force brute (sur de petites données) pour vérifier que les résultats du nouvel algorithme sont corrects.
• Quand il n'y a pas mieux : Pour certains problèmes très difficiles (dits "NP-difficiles"), la force brute est parfois la seule approche connue pour garantir la solution optimale.

Conclusion

Aujourd'hui, nous avons exploré l'approche par force brute, la stratégie de résolution de problèmes la plus directe. Bien qu'elle soit souvent inefficace, elle constitue une base essentielle.

Points clés à retenir :

• Une solution par force brute consiste à énumérer et tester toutes les possibilités.
• On l'identifie souvent par des boucles imbriquées qui génèrent toutes les combinaisons d'éléments.
• Sa complexité est souvent polynomiale (ex: $O(n^2)$, $O(n^3)$) ou pire, comme factorielle ($O(n!)$), ce qui la rend impraticable pour de grandes tailles de données.
• L'évaluation de sa complexité se fait en comptant le nombre d'opérations, qui est directement lié au nombre de combinaisons générées.
• Malgré son coût, elle reste une stratégie utile comme solution de base, pour la validation ou lorsque la taille des données est faible.

Maintenant que nous savons concevoir une première solution simple et évaluer son (souvent mauvais) rendement, la question logique est : "Comment faire mieux ?". C'est précisément l'objet de notre prochaine leçon, où nous aborderons les techniques d'optimisation pour transformer un algorithme inefficace en une solution performante.