Scribd
Importer
24 vues2 pages

Complex It É

Le document traite de la complexité des algorithmes, en se concentrant sur la complexité temporelle et en présentant des exemples concrets. Il explique la complexité linéaire avec un algorithme de recherche de minimum et la complexité quadratique avec l'algorithme de tri par sélection. Enfin, il mentionne que ces algorithmes appartiennent à une classe plus générale de complexité polynomiale.

Transféré par

ihesoussecanva
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats DOCX, PDF, TXT ou lisez en ligne sur Scribd
24 vues2 pages

Complex It É

Le document traite de la complexité des algorithmes, en se concentrant sur la complexité temporelle et en présentant des exemples concrets. Il explique la complexité linéaire avec un algorithme de recherche de minimum et la complexité quadratique avec l'algorithme de tri par sélection. Enfin, il mentionne que ces algorithmes appartiennent à une classe plus générale de complexité polynomiale.

Transféré par

ihesoussecanva
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats DOCX, PDF, TXT ou lisez en ligne sur Scribd

1) Introduction:

La complexité des algorithmes est une notion qui nous renseigne sur le temps d’exécution des
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 algorithme simple de recherche de minimum dans un tableau t de taille n,


notre programme s'écrit alors :

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

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

On tout donc cet algorithme 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élection 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 :)

Vous aimerez peut-être aussi