Introduction

Trouver un algorithme qui résout un problème, c'est trouver une succession d'opérations qui permet de fournir une solution de ce problème. Ce n'est pas toujours une chose facile, mais ce qui peut être encore plus difficile et surtout bien plus intéressant, c'est de trouver un algorithme qui fournit cette solution rapidement.

Avec la description de chacun des problèmes proposés sur ce site, on vous fournit une limite de temps : la durée maximale autorisée d'exécution de votre programme. Si votre code ne fournit pas sa réponse dans cette limite pour un test donné, ce test est considéré comme étant un échec, même si avec plus de temps, votre programme aurait pu fournir une réponse juste. Toute la difficulté est donc de faire en sorte que votre programme soit suffisamment rapide.

Le but de ce cours et de la série d'exercices qui l'accompagne est de vous montrer pourquoi certains algorithmes sont plus rapides que d'autres, et surtout de vous apprendre à déterminer approximativement la vitesse d'un algorithme avant même de le tester, grâce à un outil dont nous vous présentons les principes de base : le calcul de la complexité en temps d'un algorithme.

Ce cours contient des exemples en langages C++ et Caml, mais il n'est pas nécessaire de connaître l'un de ces deux langages pour pouvoir le suivre.

Temps d'exécution d'un programme

Si vous n'avez jamais fait d'algorithmique, vous avez probablement écrit de nombreux programmes sans jamais vous occuper de leur vitesse d'exécution. Certains de vos programmes contenaient peut-être parfois des boucles infinies et ne se terminaient jamais, mais pour le reste, ils fonctionnaient probablement toujours assez rapidement.

Prenons pour commencer l'algorithme suivant :

   Lire un entier A
   Calculer A * A, et Stocker le résultat dans B
   Calculer B * 5 + 3, et Stocker le résultat dans C
   Afficher C

Si vous écrivez le programme correspondant dans le langage de votre choix, puis l'exécutez, le résultat sera affiché immédiatement après que l'utilisateur ait entré un entier. Vous pourriez ajouter des centaines d'autres lignes de calcul du même type, le résultat arriverait toujours immédiatement : une machine récente est en effet capable d'exécuter plusieurs dizaines de millions de telles instructions en moins d'une seconde.

Exercice : essayez d'écrire un programme qui met suffisamment de temps à s'exécuter pour que le résultat ne soit pas immédiat. Attention : le programme doit être actif pendant toute son exécution, il ne s'agit pas d'appeler une fonction du langage qui ne fait qu'attendre un temps donné.

Solution :

Le moyen le plus simple de faire travailler la machine suffisamment longtemps pour que le programme ne se termine pas immédiatement, consiste à lui demander de compter jusqu'à une valeur très élevée, par exemple cent millions :

   Pour compteur allant de 1 à 100*1000*1000
      ne rien faire

Testez alors avec différentes valeurs limites pour le compteur, observez comment évolue ce temps d'exécution en fonction de cette valeur, et essayez d'en déduire une règle. La limite de temps étant fixée à une seconde, vous aurez une erreur de type "Dépassement de la limite de temps", si vous allez au delà de cette durée.

Solution :

Voici une version C++ de ce programme :

#include <stdio.h>
int main()
{
   int N, increment, compteur;
   scanf("%d%d", &N, &increment);
   for (compteur = 1; compteur <= N; compteur += increment)
      ;
   printf("%d\n", compteur);
   return 0;
}

Version Caml :

   let n = read_int() in
   let increment = read_int() in
   let total = ref 0 in
   for compteur = 1 to n do
      total := !total + increment
   done;
   print_int !total

Pour éviter que le compilateur ne remarque que la boucle ne fait rien d'utile, et qu'elle peut être remplacée par une simple instruction compteur = N, on fait lire au programme la valeur de N, et la valeur de l'incrément, sur l'entrée standard. Il devient alors bien plus difficile d'optimiser la boucle, et celle-ci est entièrement exécutée. On utilisera systématiquement 1 comme valeur de l'incrément, dans nos tests.

Sur notre serveur, au moment de l'écriture de ces lignes, les temps d'exécution de la version C++ en fonction de N sont les suivants :

A partir de ces chiffres, on peut ainsi estimer que le temps d'exécution du programme, sur cette machine, est égal à N*8*10^-10. La machine exécute donc environ 1.2 milliard d'itérations par seconde.

Le temps d'exécution est proportionnel à la valeur de N, donc proportionnel au nombre d'itérations de la boucle.

Si vous le souhaitez, vous pouvez aussi tester directement chez vous :

• En C/C++, utilisez la fonction clock() définie dans time.h, qui renvoie un nombre de ticks d'horloge processeur. Divisez par la constante CLOCKS_PER_SEC pour obtenir une valeur en secondes. Appelez cette fonction au début et à la fin de votre programme, et affichez la différence pour connaître le temps écoulé. Attention : sous Windows, la précision est assez faible.

• En Caml, vous pouvez appeler :

  print_float (Sys.time());

  Cette instruction affichera le temps écoulé depuis le début du programme. Utilisez le compilateur ocamlopt pour générer du code natif, et avoir des résultats raisonnables.

• Sous Unix, quel que soit le langage, utilisez time avec en paramètre votre programme exécutable. Vous verrez alors trois temps s'afficher, celui qui vous intéresse est le temps "user".

Dans cet exemple, on n'a fait que compter. Que se passe-t-il si en plus de compter, on effectue un autre calcul, par exemple additionner toutes les valeurs par lesquelles on passe :

   N = 100*1000*1000
   total = 0
   Pour compteur allant de 1 à N
      total = total + compteur
   Afficher total

Exercice : testez le temps d'exécution d'un programme basé sur cet algorithme, et comparez les résultats aux précédents.

Remarque : si vous utilisez un entier sur 32 bits pour stocker le total, la valeur n'aura pas trop de sens car la capacité est très vite dépassée. Cela n'a cependant pas d'importance ici, nous nous intéressons uniquement au temps d'exécution.

Le source C++ correspondant est :

#include <stdio.h>

int main()
{
   int N, increment, compteur;
   scanf("%d%d", &N, &increment);
   int total = 0;
   for (compteur = 1; compteur <= N; compteur += increment)
      total++;
   printf("%d\n", total);
   return 0;
}

Version Caml :

   let n = read_int() in
   let increment = ref read_int() in
   let total = ref 0 in
   for compteur = 1 to n do
      incr increment;
      total := !total + !increment
   done;
   print_int !total

Voici les résultats pour la version C++, sur notre serveur :

On voit que le temps d'exécution est passé de N*8*10^-10 à N*11*10^-10, pour ce nouveau programme.

En passant de une à deux instructions dans le corps de la boucle, le temps d'exécution n'a augmenté que de 25% environ.

Temps d'exécution d'une instruction

Pour bien comprendre ce qui se passe exactement, le meilleur moyen est de regarder en détail ce que le microprocesseur va exécuter à chaque boucle. On peut pour cela utiliser une option qui permet de voir le code assembleur généré par le compilateur. Pour gcc comme pour ocamlopt, il s'agit de l'option -S. Notre serveur étant un pentium 4, il s'agit donc d'assembleur x86.

Voici l'extrait correspondant à la boucle, avec des commentaires pour chaque instruction (rassurez-vous, on ne va pas vous demander d'apprendre l'assembleur). La commande complète utilisée dans le cas du C++ est : gcc boucle.c -S -O2, qui génère un fichier boucle.s. L'option -O2 indique le niveau d'optimisation, qui est celui utilisé par défaut sur notre serveur.

// label L5
.L5:
   // ajoute le contenu du registre eax, au registre edx
   addl    %eax, %edx
   // incrémente de 1 le contenu du registre eax
   incl    %eax
   // compare le contenu de eax à la valeur 100000000
   cmpl    $100000000, %eax
   // saute au label L5 si eax était inférieur ou égal à la valeur
   jle     .L5

On voit ici que la boucle contient quatre instructions du langage machine, dont une correspondant à notre instruction "total = total + compteur".

On pourrait en déduire que l'augmentation devrait être de 33%, et non 25%, mais si l'on regarde le code généré pour la boucle du premier programme, on voit que c'est pire que cela, la boucle ne contenait que deux instructions :

.L5:
   // Décrémente le contenu du registre eax
   decl    %eax
   // saute au label L5, si on est passé en dessous de zéro
   jns     .L5

Dans le cas du premier programme, le compilateur a détecté qu'il était plus efficace de compter dans l'autre sens (partir de 100 millions, et descendre jusqu'à 0) ! Cela ne correspond pas à ce que l'on avait écrit. Le programme fonctionne cependant correctement, car le compilateur va en fait appeler printf en lui passant la valeur N directement, et non la valeur du compteur. Le compilateur, lorsque les options d'optimisation sont activées (et c'est ce que nous souhaitons), peut donc faire un certain nombre de manipulations sur notre programme lors de la transformation en code exécutable, ce qui ne facilite pas la prédiction du temps d'exécution.

Si la boucle exécutée par le microprocesseur fait deux instructions dans le premier cas, et quatre dans l'autre, pourquoi le temps d'exécution n'augmente que de 25 pour cent, au lieu de doubler ? La réponse est toute simple : les temps d'exécution des différentes instructions du micro-processeur ne sont pas tous les mêmes.

Lorsque l'on parle de la fréquence d'un microprocesseur, on fait référence au nombre de cycles qu'il est capable d'exécuter en une seconde. Un microprocesseur ayant une fréquence de 1Ghz peut ainsi exécuter un milliard de cycles par seconde. A chaque cycle, le processeur exécute une étape de l'exécution d'une instruction, par exemple : la lire en mémoire, ou la décoder, écrire le résultat, etc. Les processeurs actuels peuvent manipuler plusieurs instructions en même temps, donc exécuter lors du même cycle, une étape de chacune des instructions qu'il est en train de traiter (par exemple, il peut lire en mémoire l'instruction suivante à la même étape que l'écriture du résultat de l'instruction courante).

Il faut toujours plusieurs cycles processeurs pour exécuter entièrement une instruction, mais sur un certain nombre d'instructions consécutives, dont une partie de l'exécution est faite en parallèle, le temps moyen d'exécution d'une instruction peut être bien inférieur, et ne faire qu'un cycle, parfois même moins, mais parfois bien plus, selon le type d'instructions.

Prévoir précisément le temps que va prendre un programme est en fait très difficile : d'une part compter le nombre d'instructions ne suffit pas, car différentes instructions demandent un temps différent, d'autre-part, le compilateur peut transformer radicalement notre programme, ce qui fait que nous ne pouvons même pas prévoir le nombre exact d'instructions exécutées. En pratique, le temps d'exécution des instructions dépend de nombreux facteurs, et on ne peut donner que des approximations

Pour se faire une idée des temps d'exécutions de différents types d'instruction, le plus simple reste donc l'expérimentation.

Exercice : écrivez des programmes permettant d'estimer le temps d'exécution d'une addition, puis d'une multiplication, d'une division, d'un modulo, d'une lecture et d'une écriture en mémoire (dans un tableau). Evaluez les temps d'exécution de chacun de ces programmes.

Solution :

pour pouvoir mesurer le temps d'exécution d'un certain type d'instruction uniquement, on peut faire une boucle où à chaque itération de cette boucle, on fait un certain nombre de fois cette opération. Le temps consacré à la boucle elle-même devient alors négligeable devant le temps consacré à l'instruction elle-même. Ainsi, pour tester la multiplication, on pourra écrire :

#include <stdio.h>;

int main()
{
   const int N = 10*1000*1000;
   int total = 1;
   int compteur;
   for (compteur = 1; compteur <= N; compteur++)
   {
      total = total * compteur;
      total = total * compteur;
      total = total * compteur;
      total = total * compteur;
      total = total * compteur;
      
      total = total * compteur;
      total = total * compteur;
      total = total * compteur;
      total = total * compteur;
      total = total * compteur;
   }
   printf("%d\n", total);
   return 0;
}

Version Caml correspondante

   let n = 10*1000*1000 in
   let total = ref 1 in
   for compteur = 1 to n do
      total := !total * compteur;
      total := !total * compteur;
      total := !total * compteur;
      total := !total * compteur;
      total := !total * compteur;

      total := !total * compteur;
      total := !total * compteur;
      total := !total * compteur;
      total := !total * compteur;
      total := !total * compteur;
   done;
   print_int !total

Sur une machine à 1Ghz, le programme C++ s'exécute en environ 1 seconde, ce qui montre qu'une multiplication prend de l'ordre de 10 cycles à s'exécuter. On peut donc exécuter 100 millions de multiplications par seconde. Vous pouvez appliquer le même principe pour les autres opérations, en remplaçant "total = total * compteur" par :

• total = total / compteur; pour tester la division
• total = total % compteur; pour tester le modulo
• int index = compteur % 100000; au début, puis
  total = tab[index]; pour tester la lecture en mémoire (où tab est un tableau de 100000 entiers).
• tab[index] = compteur; pour tester l'écriture en mémoire.

Faites ces différents tests chez vous, et n'hésitez pas à en imaginer d'autres pour vous familiariser avec les temps d'exécution. Rappelez-vous que les règles que vous pouvez en tirer ne sont que des approximations, beaucoup de facteurs peuvent influencer le résultat.

De manière générale, lorsque le corps de la boucle contient entre 10 et 20 instructions, on pourra estimer en première approximation qu'on peut effectuer de l'ordre de 10 millions d'itérations de cette boucle en une seconde, toujours sur une machine à 1Ghz.

Notion de complexité

Si l'on ne peut pas calculer précisément le temps d'exécution d'un programme, on peut cependant savoir comment il va évoluer en fonction des données : dans notre exemple, on sait que le temps d'exécution est proportionnel à la valeur de N, ce qui est déjà une information très utile. Si on multiplie N par 10, le temps d'exécution sera également multiplié par 10.

Prenons un autre exemple : plutôt que de compter jusqu'à 100 millions, comptons dix mille fois de suite jusqu'à dix mille :

   N = 10*1000
   total = 0
   Pour compteur1 allant de 1 à N
      Pour compteur2 allant de 1 à N
         total = total + 1
   Afficher total

On va donc compter jusqu'à 10 000 avec le compteur 1, et pour chaque itération, on compte jusqu'à 10 000 avec le compteur 2.

Exercice : déterminez la valeur affichée par l'algorithme, ainsi qu'une estimation du temps d'exécution de ce programme une fois écrit dans le langage de votre choix. Testez ensuite ce programme, et comparez le résultat à votre prédiction.

Solution :

La boucle sur le compteur 1 va être exécutée 10 000 fois, et à chaque fois, la boucle sur le compteur 2 sera exécutée 10 000 fois également. On aura donc au total 100 millions d'exécutions du corps de la boucle interne, donc total sera incrémenté 100 millions de fois et le résultat affiché sera 100000000. On peut estimer que le temps sera comparable à un programme qui compte simplement jusqu'à 100 millions, donc environ 0.11 seconde sur notre machine à 1Ghz. Voici le programme C++ correspondant :

#include <stdio.h>

int main()
{
   const int N = 10*1000;
   int total = 0;
   for (int compteur1 = 1; compteur1 <= N; compteur1++)
      for (int compteur2 = 1; compteur2 <= N; compteur2++)
         total++;
   printf("%d\n", total);
   return 0;
}

Version Caml correspondante :

   let n = 10*1000 in
   let total = ref 0 in
   for compteur1 = 1 to n do
      for compteur2 = 1 to n do
         total := !total + 1
      done
   done;
   print_int !total

Un test confirme que le programme (la version C++) affiche la valeur 100 millions, et s'exécute en 0.11 seconde, comme prévu.

Question : si l'on multiplie par 2 la valeur de N, quel sera le nouveau temps d'exécution ?

Réponse : on effectue 20000 fois la boucle externe, et à chaque fois, 20000 fois la boucle interne, soit 400 millions. On a donc multiplié par 4 le nombre d'itérations, donc le temps sera de 0.44 seconde environ. Un test donne une durée de 0.45 seconde, ce qui confirme notre prédiction.

Le temps d'exécution n'est ici plus proportionnel à N, mais à N*N, ou N². Si l'on multiplie N par 10, on multipliera ainsi le temps d'exécution par 100. Si on fait cette fois un essai avec N = 1 milliard, on aura un temps d'exécution de l'ordre de 11 milliards de secondes, c'est à dire de l'ordre de 350 ans. Inutile donc de tester avant de continuer.

Déterminer que le temps d'exécution de notre algorithme est proportionnel à N² est ce que l'on appelle déterminer la complexité en temps de cet algorithme, cette complexité étant dans ce cas O(N²). Nous verrons plus tard ce que signifie précisément cette notation O(N²), qui se lit "Grand O de N carré", considérez simplement que cela veut dire "temps d'exécution à peu près proportionnel à ...". Cette notion de complexité n'a rien à voir avec le fait que le programme soit compliqué ou non, et n'est qu'une indication sur le temps que prendra l'algorithme à s'exécuter. On dira souvent "cet algorithme est en O(N²)", ou même pour simplifier "cet algorithme est en N²". Nous verrons également qu'il existe une complexité en mémoire, qui donne une indication de la quantité de mémoire utilisée par un programme.

La complexité d'un algorithme est la partie du calcul de son temps d'exécution qui est indépendante des détails d'implémentation, du langage utilisé, du compilateur, du microprocesseur, des options d'optimisation, etc. Elle permet donc de comparer la vitesse de deux algorithmes, sans se préoccuper des considérations d'implémentation. Pour une valeur suffisamment grande de N, un algorithme de complexité O(N) sera toujours bien plus rapide qu'un algorithme de complexité O(N²), et ce quel que soit le langage, ou le micro-processeur utilisé.

Exercice : déterminez la complexité de l'algorithme suivant, et donnez une estimation de son temps d'exécution si N vaut 1000

   total = 0
   Pour compteur1 allant de 1 à N
      Pour compteur2 allant de 1 à N
         Pour compteur3 allant de 1 à N
            total = total + 1

Réponse : nous avons trois boucles imbriquées, chacune allant jusqu'à N, soit N*N*N exécutions de la boucle la plus interne, donc une complexité de O(N³). Si N vaut 1000, nous aurons donc 1 milliard d'exécutions de la boucle la plus interne, donc un temps d'exécution d'environ 1.1 seconde une fois programmé en C++, comme décrit plus haut.

Revenons maintenant à notre premier algorithme, mais en le modifiant très légèrement :

   Pour compteur1 allant de 1 à N + 1
      ne rien faire

Quelle est la complexité en temps d'un tel algorithme ? Vous avez peut-être envie de répondre O(N+1) ? En fait on dira toujours que la complexité est de O(N), car le temps d'exécution est toujours "à peu près proportionnel à N". Dès que la valeur de N est suffisamment grande, ajouter 1 devient négligeable, donc on l'ignore. Ceci vaut que la valeur ajoutée soit 1 ou toute autre valeur constante : si l'on fait aller le compteur jusqu'à N + 1 milliard, le 1 milliard deviendra négligeable dès que N dépasse quelques dizaines de milliards. Quand on calcule une complexité, considère toujours ce qui se passe pour des valeurs "suffisamment grandes" des variables dont dépend le programme.

Que diriez-vous maintenant de la complexité de l'exemple suivant :

   total = 0
   Pour compteur1 allant de 1 à N
      Pour compteur2 allant de 1 à N
        total = total + 1
   Pour compteur3 allant de 1 à N
      total = total + 1

Réponse : la boucle interne de la première partie va s'exécuter N² fois, et la boucle de la deuxième partie va s'exécuter N fois. On pourrait donc penser que la complexité est en O(N² + N), mais ici encore, pour une valeur suffisamment grande de N, N devient négligeable par rapport à N², et le temps d'exécution est à peu près proportionnel à N². La complexité de l'algorithme est donc de O(N²).

Selon le même principe, un algorithme contenant une boucle de N/2 itérations aura une complexité de O(N), et un algorithme contenant N³ + 2*N² itérations aura une complexité de O(N³).

Complexité en fonction de plusieurs variables

Dans tous nos exemples précédents, le temps d'exécution de nos algorithmes ne dépendait que d'une variable : N. Ce n'est pas toujours le cas, prenons par exemple l'exemple suivant :

   total = 0
   Pour compteur1 allant de 1 à N
      Pour compteur2 allant de 1 à P
         total = total + 1

Dans ce cas, on a au total N*P itérations, ce qui donne donc une complexité de O(N*P).

Exercice : quelle est la complexité de l'algorithme suivant :

   total = 0
   Pour compteur1 allant de 1 à N * 2
      Pour compteur2 allant de 1 à N
        total = total + 1
   Pour compteur3 allant de 1 à P
      total = total + 1
   Pour compteur4 allant de 1 à 10
      total = total + 1

Réponse : le nombre total d'itérations est de 2*N² + P + 10. A partir d'une certaine valeur de N ou de P, 10 devient négligeable, et n'est donc pas considéré pour la complexité. De même, la constante multiplicative 2 n'est pas conservée. On pourrait avoir envie de dire que pour une certaine valeur de N, P devient négligeable devant N². On ne peut cependant faire aucune supposition sur la valeur de P, qui peut être bien plus grand que N² dans certains cas. On conserve donc P dans la complexité obtenue : O(N² + P).

Prenons un nouvel exemple :

   total = 0
   donnees est un tableau de N valeurs entières
   Pour compteur1 allant de 1 à N
      valeur = donnee[compteur1]
      Pour compteur2 allant de 1 à valeur
         total = total + 1

Exercice : Quelle est la complexité de cet algorithme ?

Réponse : le nombre d'itérations dépend cette fois du contenu de chacune des cases du tableau. Le nombre de cases du tableau étant défini par une variable, on ne peut pas simplement lister une par une toutes ces valeurs dans le calcul de la complexité. Le seul moyen est ici de définir une nouvelle variable P, représentant la valeur maximale pouvant être stockée dans le tableau. Une fois cette variable définie, la complexité peut alors être définie comme O(N*P).

On pourrait dire que cette complexité n'est pas forcément la bonne : supposons que toutes les valeurs du tableau soient toujours très petites, par exemple inférieures à 100, sauf l'une d'entre elles, qui peut prendre des valeurs jusqu'à plusieurs milliards. Dans ce cas, le temps de calcul n'est pas du tout proportionnel à N*P, mais simplement proportionnel à P, ce qui contredit notre complexité de O(N*P).

Notre complexité ne définit en fait pas que le temps de calcul sera toujours proportionnel à N*P, mais qu'il est possible, avec certaines données, qu'elle atteigne un temps de calcul correspondant à cette règle de proportionnalité. On parle ainsi de complexité en temps en pire cas : le temps d'exécution le plus long qu'il soit possible d'avoir pour des valeurs de N et P données, est proportionnel à N*P. Il existe aussi une complexité dite en cas moyen, dont nous verrons la signification plus tard. La complexité en pire cas est celle qui nous intéressera le plus souvent.

Bien sûr, l'exemple décrit plus haut peut se réécrire de manière beaucoup plus efficace, pour un même résultat :

   total = 0
   donnees est un tableau de N valeurs entières
   Pour compteur1 allant de 1 à N
      total = total + donnee[compteur1]

Cette nouvelle version ne contient plus qu'une boucle de N itérations, il s'agit donc d'un algorithme de complexité O(N). Nous avons donc deux algorithmes qui effectuent la même tâche, mais avec une complexité différente. Nous pouvons sans hésiter dire que la version en O(N) est bien plus rapide que la version en O(N*P), et ce sans jamais avoir estimé le temps d'exécution réel de l'implémentation de ces deux algorithmes. Quels que soient les détails d'implémentation, le langage utilisé, ou le compilateur, etc. on sait déjà que pour des valeurs suffisamment élevées de P et N, le deuxième algorithme sera plus rapide que le premier. Ce type de comparaisons est l'objectif principal de la notion de complexité : permettre de comparer la vitesse de différents algorithmes pour le même problème.

Conclusion

Nous avons vu que le temps d'exécution d'un programme dépendait de nombreuses choses, principalement :

• Du type et de la fréquence du microprocesseur utilisé.
• Du langage utilisé et du compilateur choisi, ainsi que de ses réglages.
• Des données d'entrée
• De la complexité en temps de l'algorithme

Ces nombreux paramètres font qu'on ne peut obtenir qu'une approximation grossière du temps d'exécution, pour des valeurs d'entrée données. Le calcul de la complexité en temps nous fournit cependant un bon moyen pour comparer plusieurs algorithmes entre eux, avant même de les avoir implémentés et testés.

Pour déterminer la complexité d'un algorithme, plusieurs étapes sont nécessaires :

1. Déterminer de quelles variables le temps de calcul dépend. La complexité sera exprimée comme une fonction de ces variables.

2. Etablir une première version de la formule, en considérant toutes les boucles. La complexité d'une boucle est généralement égale à la complexité de l'algorithme exécuté à l'intérieur de la boucle, multipliée par le nombre d'itérations de la boucles.

3. Eliminer tout ce qui ne change pas la proportionnalité, ou devient négligeable pour des valeurs suffisamment grandes des variables : constantes additives, multiplicatives, etc.

Le calcul de la complexité en temps d'un algorithme est parfois bien plus compliqué que dans les exemples que nous avons vus plus haut. Nous vous proposons quelques exercices pour vous entraîner, mais une fois que vous aurez bien assimilé les notions de base, le meilleur moyen d'apprendre à manier ce concept, est de l'utiliser régulièrement.

Désormais, pour tous les problèmes que vous résoudrez sur le site, entraînez vous à calculer la complexité de votre algorithme, avant même de l'implémenter. Déduisez-en une estimation du temps d'exécution de votre programme dans les cas extrêmes, et vérifiez qu'il est inférieur à la limite de temps du sujet. En général la correction contiendra une évaluation de la complexité de l'algorithme; vous apprendrez ainsi à calculer des complexités de toutes sortes, au fur et à mesure de votre apprentissage de l'algorithmique.

Exercices :

Une série d'exercices est prévue pour compléter ce cours. Lorsqu'elle sera prête, elle apparaîtra dans la section algorithmique, niveau 1.