La complexité

Calcul de complexité, pour quoi faire?

Nous allons dans cette partie introduire la notion de complexité algorithmique, sorte de quantification de la performance d'un algorithme.

L'objectif premier d'un calcul de complexité algorithmique est de pouvoir comparer l’efficacité d’algorithmes résolvant le même problème. Dans une situation donnée, cela permet donc d'établir lequel des algorithmes disponibles est le plus optimal.

Ce type de question est primordial, car pour des données volumineuses la différence entre les durées d'exécution de deux algorithmes ayant la même finalité peut être de l'ordre de plusieurs jours.

Les règles que nous utiliserons pour comparer et évaluer les algorithmes devront respecter certaines contraintes très naturelles. On requerra principalement qu'elles ne soient pas tributaires des qualités d'une machine ou d'un choix de technologie.

Nous allons donc effectuer des calculs sur l’algorithme en lui même, dans sa version "papier". Les résultats de ces calculs fourniront une estimation du temps d’exécution de l’algorithme, et de la taille mémoire occupée lors de son fonctionnement.

Coût d'un algorithme

Le coût d'un algorithme est l'ordre de grandeur du nombre d'opérations arithmétiques ou logiques que doit effectuer un algorithme pour résoudre le problème auquel il est destiné.

Cet ordre de grandeur dépend évidemment de la taille $N$ des données en entrée.

On parlera de coût linéaire s'il est "d'ordre" $N$, de coût quadratique s'il est "d'ordre" $N^2$.

Petite réflexion pour comprendre la notion:

Comment savoir quel algorithme est plus efficace?

Voici deux algorithmes de recherche d'un élèment elt dans un tableau tab:

algo 1
recherche (elt,tab)
i=1
si elt = tab(i)
    alors vrai
sinon i = i + 1
jusqu'à i > taille(tab)
    alors faux
algo 2
recherche (elt,tab)
t = taille (tab)
pour i allant de 1 à t
    si x = tab (i)                                       
        alors vrai                                
alors faux
Quel est l'algorithme le plus optimal parmi ces deux propositions?

Considérons qu'une "opération" coûte une unité de temps

Graphique illustrant les différentes complexité et l'impact sur le coût

Calcul de complexité.


Règles générales

Pour calculer la complexité, nous allons devoir examiner chaque ligne de code et lui attribuer un coût en temps.

Le coût ainsi obtenu n'aura pas d'unité, il s'agit d'un nombre d'opérations dont chacune aurait le même temps d'exécution :1.

Les opérations qui vont devoir être comptabilisées sont :

  • Les affectations comptent pour 1 unité de temps: 
    a←2
  • Les comparaisons comptent pour 1 unité de temps: 
     2<3
  • L'accès aux mémoires comptent pour une 1 unité de temps : 
     Lire a
  • Chaque opération élémentaire comptent pour une 1 unité de temps : 
     3+2

Déterminer le coût de la ligne de code suivante : 
a←a+1

Algorithmes sans structure de contrôle

Déterminer la complexité T(n) de cet algorithme écrit en python. 
1 def conversion(n:float)->lst:
            2	h = n // 3600
            3	m = (n - 3600*h) // 60
            4	s = n % 60
            5	return h,m,s
On ne comptera pas la ligne 1 et 5. Dans la suite quand on s'intéressera à la complexité d'un algo écrit en Python nous ne prêterons pas attention à la ligne de définition de la fonction et au return.

Algorithmes avec structure conditionnelle.

La fonction suivante calcule $(-1)^n$ sans effectuer de produit mais en utilisant un test avec une alternative : 
1 def puissanceMoinsUn(n:int)->int:
            2 	if n%2==0:
            3 		res = 1
            4 	else:
            5 		res = -1
            6	return res
Déterminer la complexité $T(n)$ de cet algorithme

Algorithmes avec structure itérative.

cet fonction utilise une structure for pour calculer la somme des $n$ premiers entiers 
1 def sommeEntiers(n):
            2 	somme = 0
            3 	for i in range(n+1):
            4 		somme += i
            5 	return somme
Déterminer la complexité T(n) de cet algorithme.

La complexité de cet algorithme est dite linéaire. Ce sera le cas de tous les algorithmes avec $T(n)=an+b$ où $a$ et $b$ sont des réels.

Algorithmes avec deux structures itératives imbriquées.

1 def trouvemot(mots:lst, fichier_test:lst)->lst:
            2 	resultat=[]
            3 	for mot in mots:
            4 		for ligne in fichier_test:
            5 			if mot in ligne:
            6				resultat.append(mot)
            7	return resultat
Déterminer la complexité $T(n)$ de cet algorithme en considérant que la taille des listes mots et fichiers_test sont de $n$.

La complexité de cet algorithme est dite quadratique. Ce sera le cas de tous les algorithmes avec $T(n)=an^2+bn+c$ où $a$, $b$ et $c$ sont des réels.

La complexité algorithmique est une notion qui peut être plus complexe que ce que nous venons de voir, nous n'irons pas plus loin dans ce cours. Nous retravaillerons cette notion dans les cours d'algorithmique de première et de terminale.

Savoir faire et Savoir

  • Déterminer la complexité d'un algorithme en temps dans des cas linéaires et quadratiques.
  • Complexité linéaire
  • Complexité quadratique

Sitographie

Voici une liste de sites traitant de la complexité :

Et voici la correction: