Il faut distinguer cela de la th\u00e9orie de la complexit\u00e9 computationnelle<\/strong> (informatique th\u00e9orique). La th\u00e9orie de la complexit\u00e9 ne s\u2019int\u00e9resse plus \u00e0 un algorithme en particulier, mais au probl\u00e8me lui-m\u00eame : quelle est la difficult\u00e9 intrins\u00e8que de ce probl\u00e8me ?<\/em> On cherche \u00e0 classifier les probl\u00e8mes<\/strong> (et non les algorithmes individuels) selon les ressources minimales n\u00e9cessaires pour les r\u00e9soudre. Par exemple, on distingue la classe des probl\u00e8mes r\u00e9solus en temps polynomial (classe P<\/strong>) de ceux pour lesquels aucun algorithme polynomial n\u2019est connu (classe NP<\/strong> etc.). Cette th\u00e9orie introduit des classes de complexit\u00e9 et \u00e9tudie leurs relations (fameuse question P vs NP, etc.). Complexit\u00e9 algorithmique<\/strong> et complexit\u00e9 computationnelle<\/strong> sont li\u00e9es, mais \u00e0 des \u00e9chelles diff\u00e9rentes : la premi\u00e8re analyse des algorithmes concrets, la seconde classe des probl\u00e8mes abstraits par difficult\u00e9. Dans cet article, nous nous concentrerons sur l\u2019analyse de la complexit\u00e9 des algorithmes et sur les outils pour l\u2019estimer.<\/p>\n\n\n\n Deux des mesures de complexit\u00e9 les plus courantes sont la complexit\u00e9 en temps<\/strong> et la complexit\u00e9 en espace<\/strong>. La complexit\u00e9 en temps<\/strong> d\u2019un algorithme est une fonction qui associe \u00e0 chaque taille d\u2019entr\u00e9e n<\/em> le temps de calcul n\u00e9cessaire (typiquement le nombre d\u2019op\u00e9rations \u00e9l\u00e9mentaires effectu\u00e9es). On exprime ce temps de calcul de mani\u00e8re ind\u00e9pendante<\/em> de la machine utilis\u00e9e, en comptant par exemple les it\u00e9rations, les comparaisons ou toute op\u00e9ration significative. Par convention, on \u00e9value souvent le temps d\u2019ex\u00e9cution dans le pire cas<\/strong>, c\u2019est-\u00e0-dire le nombre maximal d\u2019\u00e9tapes que l\u2019algorithme effectuera pour une entr\u00e9e de taille n<\/em> donn\u00e9e. (On peut \u00e9galement \u00e9tudier le meilleur cas<\/strong> ou le cas moyen<\/strong>, mais le pire cas donne une garantie sup\u00e9rieure sur le comportement de l\u2019algorithme.) Lorsque n<\/em> devient tr\u00e8s grand, on s\u2019int\u00e9resse surtout \u00e0 l\u2019ordre de grandeur asymptotique<\/strong> du temps d\u2019ex\u00e9cution plut\u00f4t qu\u2019aux constantes multiplicatives ; cela permet de comparer l\u2019efficacit\u00e9 de deux algorithmes sur le long terme.<\/p>\n\n\n\n De m\u00eame, la complexit\u00e9 en espace<\/strong> mesure la quantit\u00e9 de m\u00e9moire utilis\u00e9e par un algorithme en fonction de la taille de l\u2019entr\u00e9e. On \u00e9value typiquement le nombre maximal de cases m\u00e9moire occup\u00e9es simultan\u00e9ment durant l\u2019ex\u00e9cution (en plus de l\u2019entr\u00e9e elle-m\u00eame). Par exemple, un algorithme de tri en place<\/em> qui ne n\u00e9cessite que quelques variables temporaires a une complexit\u00e9 en espace faible (constante), tandis qu\u2019un algorithme qui doit copier ses donn\u00e9es aura une complexit\u00e9 en espace lin\u00e9aire en la taille de celles-ci. Comme pour le temps, on consid\u00e8re souvent le pire cas et le comportement asymptotique. Il est important de noter que temps et espace peuvent \u00eatre en compromis<\/strong> : certains algorithmes utilisent plus de m\u00e9moire pour gagner du temps, et inversement. Id\u00e9alement, on cherche des solutions \u00e9conomes \u00e0 la fois en temps d\u2019ex\u00e9cution et en utilisation m\u00e9moire.<\/p>\n\n\n\n En r\u00e9sum\u00e9, la complexit\u00e9 en temps nous indique combien de temps de calcul<\/em> demande un algorithme en fonction de n<\/em>, et la complexit\u00e9 en espace indique combien de m\u00e9moire<\/em> il requiert. Ces deux m\u00e9triques aident \u00e0 anticiper si un algorithme sera praticable sur de grandes entr\u00e9es (par exemple, un programme en temps lin\u00e9aire sera faisable sur des millions de donn\u00e9es, tandis qu\u2019un programme en temps exponentiel ne le sera plus au-del\u00e0 de quelques dizaines d\u2019\u00e9l\u00e9ments).<\/p>\n\n\n\n Pour exprimer de fa\u00e7on rigoureuse la complexit\u00e9 en fonction de n<\/em>, on utilise les notations asymptotiques<\/strong> : principalement O<\/strong> (\u00ab grand O \u00bb), \u03a9<\/strong> (om\u00e9ga) et \u0398<\/strong> (th\u00eata). Celles-ci permettent de donner des bornes sur la croissance d\u2019une fonction lorsque n<\/em> tend vers l\u2019infini, en ignorant les constantes multiplicatives et les termes de plus faible ordre. Intuitivement, on cherche \u00e0 cat\u00e9goriser une fonction de complexit\u00e9 (par exemple T(n)<\/em>) par rapport \u00e0 une fonction de r\u00e9f\u00e9rence plus simple (par exemple n<\/em>, n\u00b2<\/em>, n log n<\/em>, etc.).<\/p>\n\n\n\n En r\u00e9sum\u00e9, O<\/strong> donne une borne haute (au-dessus), \u03a9<\/strong> une borne basse (en dessous), et \u0398<\/strong> indique que la fonction de co\u00fbt est encadr\u00e9e des deux c\u00f4t\u00e9s par la m\u00eame forme (croissance \u00e9quivalente). Dans la pratique, on utilise le plus souvent le Grand O<\/strong> pour exprimer le temps de calcul maximal d\u2019un algorithme. Par exemple : \u00ab l\u2019algorithme de tri par insertion est O(n\u00b2) dans le pire cas \u00bb<\/em>. On peut parfois pr\u00e9ciser qu\u2019il est aussi \u03a9(n)<\/em> dans le meilleur cas (donn\u00e9es d\u00e9j\u00e0 tri\u00e9es), etc. Ces notations asymptotiques permettent d\u2019ignorer les constantes multiplicatives et les termes sub-dominants, ce qui donne une vision claire de l\u2019\u00e9volutivit\u00e9<\/strong> d\u2019un algorithme lorsque la taille des donn\u00e9es augmente.<\/p>\n\n\n\n Apr\u00e8s la th\u00e9orie, passons \u00e0 la pratique : examinons quelques algorithmes classiques<\/strong> et analysons leur complexit\u00e9. Nous pr\u00e9senterons pour chacun un extrait de code en Python et expliquerons comment le nombre d\u2019op\u00e9rations \u00e9volue en fonction de n<\/em>. Ces exemples concrets vont illustrer les notions de complexit\u00e9 lin\u00e9aire, logarithmique, quadratique, cubique, etc., que nous avons \u00e9voqu\u00e9es.<\/p>\n\n\n\n Commen\u00e7ons par un algorithme simple : la recherche lin\u00e9aire<\/strong> (ou s\u00e9quentielle) d\u2019une valeur dans un tableau non tri\u00e9. L\u2019id\u00e9e est de parcourir la liste \u00e9l\u00e9ment par \u00e9l\u00e9ment jusqu\u2019\u00e0 trouver l\u2019\u00e9l\u00e9ment cible (ou arriver \u00e0 la fin sans le trouver). Voici une impl\u00e9mentation Python de la recherche lin\u00e9aire :<\/p>\n\n\n\n Dans le pire des cas (par exemple, si la valeur recherch\u00e9e est absente du tableau ou se trouve en derni\u00e8re position), cette fonction parcourra toute la liste de longueur n<\/em>. Le nombre de comparaisons sera alors proportionnel \u00e0 n<\/em>. On peut donc dire que la recherche lin\u00e9aire a une complexit\u00e9 en temps O(n)<\/strong> dans le pire cas. En effet, le temps d\u2019ex\u00e9cution cro\u00eet lin\u00e9airement avec le nombre d\u2019\u00e9l\u00e9ments : si on double la taille de la liste, le temps de recherche maximal double approximativement. \u00c0 l\u2019inverse, le meilleur cas serait que la valeur soit trouv\u00e9e au tout d\u00e9but (une seule comparaison), soit un temps constant O(1). Mais sans information particuli\u00e8re sur la distribution des donn\u00e9es, on retient le pire cas lin\u00e9aire. Pour donner un ordre d\u2019id\u00e9e, chercher un nom dans un annuaire de 30 000 contacts en parcours s\u00e9quentiel n\u00e9cessitera au pire 30 000 op\u00e9rations de comparaison \u2013 ce qui est faisable, mais si l\u2019annuaire passe \u00e0 des millions de contacts, cela devient beaucoup plus long.<\/p>\n\n\n\n Supposons maintenant que l\u2019on dispose d\u2019une liste tri\u00e9e<\/em>. Peut-on chercher une valeur plus efficacement que de tout parcourir ? Oui, gr\u00e2ce \u00e0 la recherche dichotomique<\/strong> (aussi appel\u00e9e recherche binaire). Le principe est de comparer la valeur cherch\u00e9e \u00e0 l\u2019\u00e9l\u00e9ment du milieu du tableau : si la valeur cible est plus petite, on sait qu\u2019elle se trouve dans la premi\u00e8re moiti\u00e9 (puisque le tableau est tri\u00e9) ; si elle est plus grande, on ira chercher dans la seconde moiti\u00e9. En r\u00e9p\u00e9tant ce d\u00e9coupage en deux, on r\u00e9duit drastiquement le nombre de comparaisons. Voici une impl\u00e9mentation en Python :<\/p>\n\n\n\n Dans cette boucle, \u00e0 chaque it\u00e9ration on divise par deux la portion de tableau dans laquelle la valeur peut se trouver. On passe ainsi d\u2019un espace de recherche de n<\/em> \u00e9l\u00e9ments \u00e0 n\/2<\/em>, puis n\/4<\/em>, etc., jusqu\u2019\u00e0 \u00e9ventuellement trouver la valeur ou r\u00e9duire l\u2019espace \u00e0 z\u00e9ro. Le nombre d\u2019it\u00e9rations avant d\u2019arr\u00eater est d\u2019environ log\u2082(n)<\/strong> (logarithme en base 2 de n<\/em>) dans le pire des cas. Autrement dit, la complexit\u00e9 de cet algorithme en temps est O(log n)<\/strong>. Pour reprendre l\u2019exemple de l\u2019annuaire de 30 000 noms : une recherche dichotomique trouvera le nom en au plus 15 comparaisons environ (puisque 2^15 \u2248 32 768), contre 30 000 comparaisons pour la recherche lin\u00e9aire \u2013 un gain spectaculaire.<\/p>\n\n\n\n Ci-dessous, une illustration montre comment la recherche dichotomique proc\u00e8de par divisions successives de l\u2019espace de recherche : \u00e0 chaque \u00e9tape, la moiti\u00e9 des \u00e9l\u00e9ments est \u00e9limin\u00e9e.<\/p>\n\n\n\n Exemple visuel de la recherche dichotomique (binary search) qui r\u00e9duit de moiti\u00e9 l\u2019espace de recherche \u00e0 chaque \u00e9tape. Les tableaux repr\u00e9sentent la portion restante \u00e0 chaque it\u00e9ration, jusqu\u2019\u00e0 trouver la valeur cible (27) \u00e0 l\u2019indice 5.<\/em><\/p>\n\n\n\n Ainsi, la recherche dichotomique est extr\u00eamement efficace sur de grands volumes de donn\u00e9es tri\u00e9es. Cependant, elle n\u00e9cessite imp\u00e9rativement que la liste soit tri\u00e9e<\/strong> au pr\u00e9alable (ce qui, en soi, peut co\u00fbter du temps). Si les donn\u00e9es ne sont pas tri\u00e9es, on ne peut pas \u00e9liminer la moiti\u00e9 en un test, et la recherche s\u00e9quentielle O(n) reste la seule solution g\u00e9n\u00e9rale.<\/p>\n\n\n\n Consid\u00e9rons un algorithme dont les \u00e9tapes comportent deux boucles imbriqu\u00e9es<\/strong> parcourant chacune n<\/em> \u00e9l\u00e9ments. Par exemple, une double boucle qui compare tous les couples d\u2019\u00e9l\u00e9ments dans un tableau, ou qui g\u00e9n\u00e8re une table de multiplication n \u00d7 n<\/em>. Voici un petit exemple en Python :<\/p>\n\n\n\n Cette fonction effectue un incr\u00e9ment De nombreux algorithmes ont un comportement quadratique, par exemple le tri \u00e0 bulles<\/strong> (qui compare tous les couples d\u2019\u00e9l\u00e9ments adjacents) ou le tri par insertion<\/strong> dans le pire cas. Au-del\u00e0 de quelques milliers d\u2019\u00e9l\u00e9ments, une complexit\u00e9 O(n\u00b2) peut devenir probl\u00e9matique, car le temps de calcul augmente tr\u00e8s vite. Par exemple, un algorithme en n\u00b2<\/em> qui prend 1 seconde pour n = 10 000<\/em> \u00e9l\u00e9ments en prendra environ 4 secondes pour n = 20 000<\/em>, ~100 secondes pour n = 100 000<\/em>, et deviendra carr\u00e9ment impraticable pour n = 1 000 000<\/em> (un million) d\u2019\u00e9l\u00e9ments (o\u00f9 n\u00b2 = 10^12<\/em> op\u00e9rations). D\u2019o\u00f9 l\u2019importance de chercher des algorithmes plus efficients lorsque n<\/em> devient grand.<\/p>\n\n\n\n Pour illustrer une complexit\u00e9 cubique<\/strong> O(n\u00b3) et voir comment on peut parfois la r\u00e9duire, penchons-nous sur la multiplication de matrices carr\u00e9es de taille n \u00d7 n<\/em>. L\u2019algorithme standard (appris en math\u00e9matiques) multiplie deux matrices A<\/em> et B<\/em> en calculant tous les produits scalaires entre lignes de A<\/em> et colonnes de B<\/em>. En pseudo-code, cela donne trois boucles imbriqu\u00e9es :<\/p>\n\n\n\n Ici, les indices i<\/em> et j<\/em> parcourent respectivement les lignes et colonnes du r\u00e9sultat C<\/em>, et la boucle k<\/em> accumule le produit des \u00e9l\u00e9ments correspondants de la i-\u00e8me ligne de A<\/em> et de la j-\u00e8me colonne de B<\/em>. Le nombre d\u2019op\u00e9rations \u00e9l\u00e9mentaires (multiplications et additions) effectu\u00e9es est d\u2019environ n<\/em> \u00d7 n<\/em> \u00d7 n<\/em> = n\u00b3<\/strong>. Donc la complexit\u00e9 en temps de l\u2019algorithme na\u00eff de multiplication de deux matrices de dimension n<\/em> est \u0398(n\u00b3)<\/strong>. Pour donner un ordre de grandeur, multiplier deux matrices 100\u00d7100 n\u00e9cessite de l\u2019ordre de 1 000 000 d\u2019op\u00e9rations, et des matrices 1000\u00d71000 en n\u00e9cessitent 1 000 000 000 (un milliard). On comprend qu\u2019am\u00e9liorer cet ordre de complexit\u00e9 serait pr\u00e9cieux pour le calcul scientifique ou le traitement d\u2019images par exemple, o\u00f9 les matrices peuvent \u00eatre tr\u00e8s grandes.<\/p>\n\n\n\n De fait, il existe des algorithmes plus rapides que \u0398(n\u00b3)<\/em> pour la multiplication matricielle. Le premier a \u00e9t\u00e9 d\u00e9couvert par Volker Strassen<\/strong> en 1969 : l\u2019algorithme de Strassen<\/strong> utilise une approche r\u00e9cursive ing\u00e9nieuse. Son id\u00e9e est de d\u00e9couper les matrices en sous-matrices (de taille n\/2 \u00d7 n\/2) et de r\u00e9duire le nombre de multiplications n\u00e9cessaires en combinant astucieusement les r\u00e9sultats. Alors que l\u2019approche na\u00efve multiplie 8 sous-matrices (pour calculer les 4 blocs du r\u00e9sultat), Strassen parvient \u00e0 n\u2019en multiplier que 7, au prix de quelques additions suppl\u00e9mentaires. Ce gain de 1 multiplication peut para\u00eetre anodin, mais en r\u00e9appliquant la m\u00e9thode r\u00e9cursivement, le nombre total d\u2019op\u00e9rations<\/strong> suit une r\u00e9currence : T(n) = 7 T(n\/2) + O(n\u00b2)<\/em> (les O(n\u00b2)<\/em> proviennent des additions de matrices). R\u00e9soudre cette r\u00e9currence (par le Master Theorem<\/em>, que l\u2019on verra plus loin) donne un ordre asymptotique d\u2019environ O(n^log27)<\/strong>, soit O(n^2.8074\u2026)<\/strong>. Ainsi, l\u2019algorithme de Strassen a une complexit\u00e9 inf\u00e9rieure \u00e0 n\u00b3. En pratique, cela signifie que pour des matrices tr\u00e8s grandes, Strassen sera plus rapide que l\u2019algorithme classique. Par exemple, pour n = 1024, n\u00b3 \u2248 1,07\u00d710^9<\/em> op\u00e9rations tandis que n^2.807<\/em> \u2248 4.7\u00d710^8* : presque deux fois moins.<\/p>\n\n\n\n L\u2019algorithme de Strassen marque le d\u00e9but d\u2019une longue s\u00e9rie de recherches en algorithmique. Depuis 1969, d\u2019autres m\u00e9thodes de multiplication de matrices encore plus rapides (mais de plus en plus complexes) ont \u00e9t\u00e9 d\u00e9couvertes. L\u2019exposant de complexit\u00e9 a ainsi \u00e9t\u00e9 progressivement abaiss\u00e9 : 2.80, 2.78, 2.67, \u2026 jusqu\u2019\u00e0 environ 2.37<\/strong> aujourd\u2019hui. Autrement dit, on sait th\u00e9oriquement multiplier deux matrices en O(n^2.37)<\/em> environ, gr\u00e2ce \u00e0 des algorithmes tr\u00e8s sophistiqu\u00e9s. Cependant, ces am\u00e9liorations extr\u00eames \u2013 parfois qualifi\u00e9es d\u2019algorithmes galactiques<\/strong> \u2013 ne sont pas utilis\u00e9es en pratique<\/strong>. En effet, ils ne deviennent avantageux qu\u2019\u00e0 des tailles de matrices astronomiquement grandes, et leur overhead (constantes cach\u00e9es, complexit\u00e9 d\u2019impl\u00e9mentation) les rend plus lents sur les matrices de taille courante. En pratique, l\u2019algorithme de Strassen lui-m\u00eame n\u2019est utile que pour des matrices au-del\u00e0 d\u2019un certain seuil (typiquement quelques centaines ou milliers) ; en-de\u00e7\u00e0, le classique triple boucle peut \u00eatre plus rapide \u00e0 cause des optimisations CPU\/cache. Cet exemple illustre qu\u2019une meilleure complexit\u00e9 asymptotique n\u2019est pas toujours synonyme de meilleure performance r\u00e9elle sur des inputs de taille mod\u00e9r\u00e9e \u2013 mais \u00e0 tr\u00e8s grande \u00e9chelle, elle finit par l\u2019emporter. Quoi qu\u2019il en soit, la d\u00e9couverte de Strassen fut fondamentale car elle a d\u00e9montr\u00e9 que la borne n\u00b3<\/em> n\u2019\u00e9tait pas une barri\u00e8re absolue, ouvrant tout un champ de recherche en algorithmique.<\/p>\n\n\n\n La r\u00e9solution de la r\u00e9currence de l\u2019algorithme de Strassen ci-dessus nous am\u00e8ne \u00e0 un outil pr\u00e9cieux en analyse d\u2019algorithmes : le Master Theorem<\/strong> (ou th\u00e9or\u00e8me du ma\u00eetre<\/em>). Il s\u2019agit d\u2019un th\u00e9or\u00e8me qui donne, sans effort de calcul it\u00e9ratif, l\u2019ordre de grandeur asymptotique des solutions de r\u00e9currences divide-and-conquer courantes. De nombreux algorithmes r\u00e9cursifs divisent en effet le probl\u00e8me en plusieurs sous-probl\u00e8mes plus petits. Le Master Theorem consid\u00e8re les r\u00e9currences de la forme :<\/p>\n\n\n\n T(n)=a\u2005\u200aT\u2009\u2063(nb)+f(n),T(n) = a \\; T\\!\\Big(\\frac{n}{b}\\Big) + f(n),<\/p>\n\n\n\n o\u00f9 a \u2265 1<\/em> est le nombre de sous-probl\u00e8mes, b > 1<\/em> le facteur de r\u00e9duction de la taille (chaque sous-probl\u00e8me a une taille ~n\/b<\/em>), et f(n)<\/em> le co\u00fbt hors r\u00e9cursion (temps pour diviser\/recombiner les sous-probl\u00e8mes). Intuitivement, on a un arbre de r\u00e9cursion<\/strong> de hauteur ~log_b(n) o\u00f9 \u00e0 chaque niveau les a^k<\/em> appels de ce niveau traitent des probl\u00e8mes de taille n\/b^k<\/em>. Le th\u00e9or\u00e8me du ma\u00eetre fournit une solution asymptotique T(n) = \u0398(g(n))<\/em> selon la comparaison entre f(n)<\/em> et nlogba<\/em>, qui repr\u00e9sente (\u00e0 un facteur pr\u00e8s) le co\u00fbt total de tous les sous-probl\u00e8mes. On d\u00e9finit pour cela l\u2019exposant critique<\/strong> c = log_b(a)<\/em> (aussi not\u00e9 ccritique<\/em>). Trois cas se pr\u00e9sentent :<\/p>\n\n\n\nComplexit\u00e9 en temps et en espace<\/h2>\n\n\n\n
Notations asymptotiques : O, \u03a9, \u0398<\/h2>\n\n\n\n
\n
Exemples concrets de complexit\u00e9 (avec code)<\/h2>\n\n\n\n
Recherche lin\u00e9aire \u2013 Complexit\u00e9 O(n)<\/h3>\n\n\n\n
def recherche_lineaire(tableau, cible):\n for i, element in enumerate(tableau):\n if element == cible:\n return i # renvoie l'indice o\u00f9 la cible est trouv\u00e9e\n return -1 # renvoie -1 si la cible n'est pas pr\u00e9sente\n<\/code><\/pre>\n\n\n\nRecherche dichotomique \u2013 Complexit\u00e9 O(log n)<\/h3>\n\n\n\n
def recherche_dichotomique(tableau, cible):\n gauche = 0\n droite = len(tableau) - 1\n while gauche <= droite:\n milieu = (gauche + droite) \/\/ 2\n if tableau[milieu] == cible:\n return milieu # trouv\u00e9 \u00e0 l'indice milieu\n elif tableau[milieu] < cible:\n gauche = milieu + 1 # chercher dans la moiti\u00e9 droite\n else:\n droite = milieu - 1 # chercher dans la moiti\u00e9 gauche\n return -1 # non trouv\u00e9\n<\/code><\/pre>\n\n\n\n![\"\"](\"https:\/\/boissiebruno-pageperso-pi.ovh\/wp-content\/uploads\/2025\/06\/78113dfe-87c2-4d09-889d-d0b7a013e14e.png\")
<\/figure>\n\n\n\nBoucles imbriqu\u00e9es \u2013 Complexit\u00e9 O(n\u00b2)<\/h3>\n\n\n\n
def operations_quadratiques(n):\n compteur = 0\n for i in range(n):\n for j in range(n):\n compteur += 1 # op\u00e9ration constante O(1) dans la boucle interne\n return compteur\n<\/code><\/pre>\n\n\n\ncompteur += 1<\/code> pour chaque paire (i, j)<\/em> avec i<\/em> allant de 0 \u00e0 n-1<\/em> et j<\/em> de 0 \u00e0 n-1<\/em>. Il y a exactement n \u00d7 n<\/em> it\u00e9rations au total, soit n\u00b2<\/em> op\u00e9rations \u00e9l\u00e9mentaires. On en d\u00e9duit que la complexit\u00e9 en temps est O(n\u00b2)<\/strong> (croissance quadratique). En effet, le nombre d\u2019op\u00e9rations cro\u00eet comme le carr\u00e9 de n<\/em>. Pour n = 100<\/em>, on effectue 10 000 incr\u00e9ments ; pour n = 1000<\/em>, un million d\u2019incr\u00e9ments, etc. De mani\u00e8re g\u00e9n\u00e9rale, si l\u2019on double n<\/em>, le temps d\u2019ex\u00e9cution est multipli\u00e9 par ~4 (2\u00b2).<\/p>\n\n\n\nMultiplication de matrices \u2013 O(n\u00b3) vs algorithme de Strassen (~O(n^2.8))<\/h3>\n\n\n\n
def multiplication_matrices(A, B):\n n = len(A)\n C = [[0] * n for _ in range(n)]\n for i in range(n):\n for j in range(n):\n for k in range(n):\n C[i][j] += A[i][k] * B[k][j]\n return C\n<\/code><\/pre>\n\n\n\nPr\u00e9sentation du Master Theorem (Th\u00e9or\u00e8me du Ma\u00eetre)<\/h2>\n\n\n\n
\n