1) Introduction:
La complexité des algorithmes est une notion qui nous renseigne sur le temps de l'éxécution de l'algorithmes. On distingue beaucoup de classes de complexité qu'on va essayer de voir et de détailler à travers des exemples. Il existe aussi la notion de complexité en mémoire que l'on ne va pas détailler dans ce cours, mais qui est très analogue et plus simple que la complexité temporelle qu'on va étudier

2) Un premier exemple:
Considérons un algorithmes simple de recherche de minimum dans un tableau t de taille n, notre programme s'écrit alors

min:=t[1];  
for i:=2 to n do     
     if min<t[i] then min:=t[i]

 Das cette boucle, on fait n-1 passages plus une instruction avant,

On tout donc cette algorithmes fait n opérations, on dit alors qu'il est de complexité linéaire et on note O(n)

Considérons maintenant l'algorithme de tri séléction que vous trouvez ici :

procedure TriSelection(n : integer ; var t : tab);
var i, j, min, tmp : integer;
begin
   for i:=1 to n-1 do begin

      min := i;

      for j:=i+1 to n do
         if (t[j] < t[min]) then min:=j;

      if (i <> min) then begin

         tmp := t[i];
         t[i] := t[min];
         t[min] := tmp;
      end;
   end; 
end;

 Si on analyse cet algorithme on trouve que le nombre d'opérations est de n*(n-1)/2. On peut donc dire qu'il est en O(n²/2) mais vu qu'avec le notion de complexité on ne donne pas d'importance aux constantes et que la notation mathématique du O (domination), on écrit donc que l'algorithme est en O(n²) et on dit qu'il est de complexité quadratique.

Ainsi, nous avons vu les classes les plus simples de complexité : la complexité linéaire ou en O(n) et la complexité quandratique en O(n²). Ce type d'algorithme appartient en fait à une classe d'algorithme plus général qui a une complexité dite polynomiale donc en O(n^p).  On peut créer un exemple simple ayant cette complexité : typiquement p boucles imbriquées ayant chacune n itérations. Nous verrons dans les autres cours, des complexités plus complexes :)