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$.

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 le 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 le complexité $T(n)$ de cet algorithme

Algorithmes avec structure itérative.

Cette 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 le 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 le 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.

Essayons maintenant d'évaluer la complexité de nos tris par selection et par insertion

Vous allez désormais calculer la complexité de l'algorithme de tri par insertion, rappelé ci-dessous, dans le pire des cas, c'est à dire dans le cas où toutes les valeurs sont triées dans l'ordre décroissant.


def tri_insertion(lst:list)->list:
	for i in range(1,len(lst)):			# le premier élément forme seul une liste classée 
		elt=lst[i] 						# élément à classer
		j=i
		while elt < lst[j-1] and j > 0:	# permutation avec le précédent s'il est plus grand
			lst[j]=lst[j-1]     
			j-=1 
		lst[j]=elt						# placement au bon endroit
    return lst

Vous allez désormais calculer la complexité de l'algorithme de tri par sélection, rappelé ci-dessous, dans le pire des cas, c'est à dire dans le cas où toutes les valeurs sont triées dans l'ordre décroissant.

 			# Les deux fonctions étudiées précédemment :

# la fonction de recherche de l'index du minimum :
def positionner(lst: list,depart :int) -> int:
	pos = depart					# pos stocke la position du minimum : lst[pos] sera donc le minimum trouvé	
	i= pos+1
	while i<len(lst):
		if lst[i] < lst[pos]:	# cas où une valeur plus petite que le minimum est trouvée
			pos = i
		i += 1
	return pos 						# index du minimum de la liste entre depart et dernière valeur
			
# la procédure d'échange de deux termes :
def permuter(lst: list, i1: int, i2: int) -> None:
    a = lst[i1] 				# utilisation d'une variable temporaire pour stocker la valeur qui sera écrasée par remplacement par la seconde valeur
    lst[i1] = lst[i2]
	lst[i2] = a
	return None 					# aucun retour : la permutation a eu lieu sur la liste lst qui est donc modifiée.

# Tri par sélection
	def tri_selection(lst: list) -> None:
		for i in range(len(lst)-1):					# on balaie toute la liste
			pos = positionner(lst, depart=i)		# on cherche le minimum parmi les termes non encore triés
			if pos != i:							# cas où le minimum n'est pas placé juste après la partie déjà triée
				permuter(lst, i1=i, i2=pos)
	return None										# aucun retour : la permutation a eu lieu sur la liste lst qui est donc modifiée.

On considère que :

chaque affectation correspond à une opération,
chaque comparaison correspond à une opération,
chaque obtention du terme d'une liste à partir de son index correspond à une opération.

Nous allons découvrir qu'il existe des tris plus efficaces donc avec une compléxité plus réduite.

Pour les plus curieux, essayez de déterminer la complexité d'une recherche par dichotomie 😉

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: