I. Complexité¶

Cours¶

A. La notion d'algorithme¶

Les algorithmes ont existé bien avant les programmes informatiques (premiers algorithmes répertoriés par Muhammad Al Khwarizmi au 9ème siècle). Ces deux notions sont donc différentes.

Définition d'un algorithme

suite d'instructions appliquée à des données, permettant de résoudre un problème.

Plus précisément, on applique dans un ordre précis des opérations élémentaires à des données d'entrée, pour obtenir un résultat en sortie.

Compléter le schéma suivant :

graph LR
A[Valeurs d'entrée] --> F[Suite d'opérations élémentaires];
  F --> G[Valeurs de sortie]

Vocabulaire

Les valeurs d'entrée sont aussi appelées paramètres pour une fonction, et les valeurs de sortie correspondent au résultat de l'algorithme.
La suite d'opérations élémentaires est traditionnellement écrite en "langage naturel" ou pseudo-code : dans un format qui ressemble à celui du code, mais qui n'utilise pas la syntaxe d'un langage de programmation en particulier. Il peut ensuite être traduit dans n'importe quel langage.

B. Complexité d'un algorithme¶

B.I. Coût en temps et en mémoire¶

L'informatique a longtemps été limitée par les ressources nécessaires à l'exécution des programmes : les ressources en mémoire et en temps. Un algorithme doit occuper de l'espace et met un certain temps à s'exécuter : il est associé à un coût en mémoire et à un coût en temps.

Les capacités en mémoire des ordinateurs d'aujourd'hui ont largement augmenté par rapport à celles des machines du milieu du XXème siècle, elles ne limitent donc plus l'exécution d'algorithmes simples (c'est toujours une question d'actualité, notamment pour les algorithmes d'IA -d'apprentissage automatique- qui ont besoin de grandes quantités de données).

Dans ce cours, nous allons nous intéresser au coût en temps ou complexité en temps des algorithmes.

De quoi dépend le temps d'exécution d'un programme ?

Il dépend notamment des performances de son processeur de l'ordinateur sur lequel il s'exécute, et du langage de programmation utilisé.

Comment peut-on faire pour donner une mesure du temps nécessaire à exécuter un algorithme ?

Le coût en temps d'un algorithme est calculé théoriquement pour comparer les algorithmes. Nous allons compter des opérations élémentaires : toute opération faite par l'algorithme.

B.II. Complexité en temps de la recherche d'occurrences¶

On prend pour exemples les algorithmes de comptage et de recherche d'occurrence, écrits en pseudo-codes.

Exemple 1

fonction compte_occurrences(tab, v)
1    compteur <- 0
2    pour i allant du premier au dernier indice de tab
3        si tab[i] est égal à v
4            compteur <- compteur+1
     renvoyer compteur

Compter combien de fois sera exécutée chaque instruction de l'algorithme. La donner, quand cela est possible, en fonction de \(n\) : la longueur du tableau.

ligne	1	2	3	4
nombre de fois qu'elle est exécutée	1	n	n	compteur

Quelles sont les instructions qui sont exécutées le plus de fois ?

Les lignes 2 et 3 sont exécutées le plus de fois (incrémentation de i et test d'égalité entre tab[i] et v).

La complexité en temps exacte de cet algorithme est de \(2n+compteur+1\), mais nous allons nous contenter d'un ordre de grandeur : une approximation expliquant comment le nombre d'opérations évolue en fonction de la taille des données du problème, ici \(n\).

Le coût en temps de cet algorithme est ici proportionnel à \(n\), la longueur du tableau.

Cela signifie que pour exécuter l'algorithme sur un tableau de taille 50, il faudra de l'ordre de 10 fois plus de temps que pour l'exécuter sur un tableau de taille 5.

Exemple 2

fonction recherche_occurrence(tab, v)
1    trouve <- Faux
2    ind <- 0
3    tant que trouve est faux et ind < longueur(tab)
4        si tab[ind] est égal à v
5            trouve <- Vrai
6        sinon
7            ind <- ind+1
     renvoyer trouve

Compter combien de fois sera exécutée chaque instruction de l'algorithme :
- Si v se trouve dans tab, en position j :
Solution

ligne 1 2 3 4 5 6 7

nombre de fois qu'elle est exécutée 1 1 j+1 j j 1 j
- Si v ne se trouve pas dans tab :
Solution

ligne 1 2 3 4 5 6 7

nombre de fois qu'elle est exécutée 1 1 n+1 n 0 n n

Que peut-on en déduire ?

Le nombre d'opérations élémentaires dépend des données. \(j<=n\), donc on aura généralement beaucoup moins d'instructions exécutées quand v est présente dans tab.

Pour connaître les limites d'un algorithme, on s'intéresse à la complexité dans le pire des cas.

Quel est l'ordre de grandeur de cette complexité dans le pire des cas ?

Elle vaut 4n+3, elle est donc proportionnelle, ou linéaire par rapport à \(n\).

Que peut-on dire de la complexité des deux exemples, de recherche et de comptage d'occurrences ?

Les deux algorithmes ont la même complexité en temps dans le pire des cas.

B.III. Les types de complexité¶

La complexité de l'algorithme suivant dépend-elle de la taille des données d'entrée ?
```
fonction mediane(t)
    med <- t[longueur de t divisée par 2]
    renvoyer med
```
Solution

La complexité ne dépend pas de la taille des données d'entrée : dans tous les cas l'instruction ne sera exécutée qu'une fois.

La complexité est dite constante.
Exprimer la complexité de l'algorithme suivant, qui calcule la somme de tous les éléments d'une matrice m de taille \(n*n\), en fonction de \(n\).
```
fonction somme_matrice(m)
    s <- 0
    n <- longueur de m
    pour i allant du premier au dernier indice des lignes de m
        pour j allant du premier au dernier indice des colonnes de m
            s <- s + m[i][j]
    renvoyer s
```
Solution

Pour chaque valeur de i, le corps de la boucle en j s'exécute \(n\) fois. La boucle en i s'exécutant \(n\) fois aussi, l'instruction s <- s + m[i][j] s'exécute \(n^2\) fois.

La complexité est dite quadratique.

B.IV. Récapitulatif¶

On utilise la notation "grand O" pour indiquer un ordre de grandeur, valable pour \(n\) suffisamment grand.

Type	Notation	Exemple
Constante	\(O(1)\)	renvoyer une valeur (sans parcours)
Logarithmique	\(O(log(n))\)	exponentiation rapide
Linéaire	\(O(n)\)	parcours de tableau 1D
Quadratique	\(O(n^2)\)	parcours de tableau 2D

Les représenter sur le graphe suivant :

TD : Complexité¶

On conçoit un algorithme permettant de déterminer la valeur maximale parmi un tableau quelconque de valeurs comparables.

a. Ecrire un programme implémentant cet algorithme.
b. Pour une liste de 100 valeurs, le nombre minimal de comparaisons que doit effectuer cet algorithme est :

A 7
B 99
C 200
D 10000

c. Quel est alors son coût ?

A constant
B logarithmique
C linéaire
D quadratique

On considère le code suivant de recherche d'une valeur dans une liste :

def search(x, y):
    ''' Recherche la valeur x dans la liste de valeurs y '''
    for i in range(len(y)):
        if x == y[i]:
            return i
    return None

Quel est le coût de cet algorithme ?

A constant
B logarithmique
C linéaire
D quadratique

On exécute le script suivant :
```
for i in range(n):
    for j in range(i):
        print('NSI')
```
a. Combien de fois le mot NSI est-il affiché ?

A \(n^2\)
B \((𝑛 + 1)^2\)
C 1 + 2 + ⋯ + (𝑛 − 1)
D 1 + 2 + ⋯ + (𝑛 − 1) + 𝑛

b. En déduire sa complexité temporelle.

Quel code parmi les quatre proposés ci-dessous s'exécute-t-il en un temps linéaire en 𝑛 (c'est-à-dire avec un temps d'exécution majoré par 𝐴 × 𝑛 + 𝐵 où 𝐴 et 𝐵 sont deux constantes) ?

A

for i in range(n//2):
    for j in range(i+1,n):
        print('hello')

B

for i in range(n):
    print('hello')

C

L = [ i+j for i in range(n) for j in range(n) ]
for x in L:
    print('hello')

D

for i in range(n//2):
    for j in range(n//2):
        print('hello')