TD3 - Complexité algorithmique

Objectifs

1. Comprendre le concept de l'algorithmique ;
2. Être capable d'analyser la complexité de programmes simples ;
3. Comprendre l'importance de l'ordre de grandeur des programmes.

Td

L'ensemble du Td se fait sur word.

Complexité algorithmique

La complexité algorithmique permet d'estimer les ressources nécessaires à un algorithme pour résoudre un problème donné.

On distingue 2 types de complexité :

• La complexité temporelle : on estime le temps d'exécution d'un algorithme ;
• La complexité spatiale : on estime la mémoire utilisée par un algorithme.

L'étude de la complexité est importante. Elle permet de comparer plusieurs solutions à un même problème pour déterminer la plus optimale, mais elle sert également à prévoir le comportement des programmes pour des grandes données.

En NSI, on se limite à la compréhension de la complexité temporelle.

Complexité temporelle

La complexité temporelle mesure le nombre d'opérations élémentaires en fonction de la taille de l'entrée 𝑛.
Une opération élémentaire représente les opérations les plus basiques en programmation (affectation, condition ...).

Dans un algorithme, il s'agit donc de compter le nombre d'opérations effectuées :

def moyenne(liste):
    m = 0
    for element in liste :
        m += element
    m/= len(liste)
    return m

Dans ce programme, 𝑛 représente la taille de l'entrée, donc la taille de la liste. La fonction va s'exécuter plus ou moins vite, suivant la taille de cette liste. Passons au calcul des instructions :

def moyenne(liste):
    m = 0                   # 1 opération
    for element in liste :  # je parcours tous les éléments de la liste, la boucle va répéter "n" instructions
        m += element            # 1 opération
    m/= len(liste)          # 1 opération
    return m                # 1 opération

En faisant les comptes, il y a : 1 + n * (1) + 1 + 1 opérations. On peut donc dire qu'il y a n + 3 opérations dans cette fonction.

Ordre de grandeur

Dire qu'un programme fait n+3 opérations ne fait pas énormément de sens, et ne donne pas un réel visuel du temps que cela pourrait prendre.
Lorsque l'on étudie la complexité d'un algorithme, on s'exprime toujours en ordre de grandeur, pour donner une meilleure idée approchée du temps que mettrait un programme à s'exécuter.

Différents cas

Il peut y avoir différentes approches dans le calcul de la complexité. Pour estimer au plus juste le temps d'exécution d'un programme, on se place toujours dans le pire des cas.
Le pire des cas indique que l'on va toujours, dans l'algorithme, faire le plus d'instructions possibles. Cela implique donc de calculer la complexité lorsque l'algorithme exécute ce qui pourrait prendre le plus d'instruction, et donc de temps.

Il existe d'autres cas, celui qu'on appelle le meilleur des cas, et la complexité en moyenne. Le meilleur des cas ne serait pas suffisamment représentatif, et la complexité en moyenne est plus compliquée à analyser.

Dans le pire des cas, la complexité s'écrit O() avec dans les parenthèses, la valeur la plus grande de la complexité calculée. On la lit "Grand O de ..." suivi de la valeur approchée.

Avec la fonction en exemple

La fonction plus haut avait une complexité de n + 3. La valeur la plus grande étant n, on dit que le programme a une complexité de O(n).
On dit également que la complexité est linéaire.

Il existe ainsi des noms donnés à chaque type de complexité que l'on peut trouver :

Temps	Nom donné
O(1)	Constante
O(log(n))	Logarithmique
O(n)	Linéaire
O(n*log(n))	Quasi linéaire
O(n²)	Quadratique
O(n³)	Cubique
O(n!)	Factoriel

Exercice

Opération mixte

On donne le programme suivant :

def operation_mixte(L):
    for i in range(len(L)):
        print(L[i])
    for i in range(len(L)):
        if L[i]%2 == 0 :
            print("pair")
        else :
            print("impair")

1. Calculer la complexité de ce programme.
2. Quel est son ordre de grandeur ?

Palindrome

On donne la fonction palindrome suivante :

def palindrome(m) :
    i = 0
    j = len(m)-1
    pal = True
    while i <= j and pal == True :
        if m[i] == m[j] :
            i = i+1
            j = j-1
        else :
            pal = False
    return pal

1. Calculer la complexité de ce programme.
2. Quel est son ordre de grandeur ?

Tri sélection

On donne la fonction du tri par sélection :

def selection(liste):
    n = len(liste)
    for i in range(n):
        mini = liste[i]
        ind = i
        for j in range(i+1, n):
            if liste[j] < mini:
                ind = j
                mini = liste[j]
        temp = liste[i]
        liste[i] = liste[ind]
        liste[ind] = temp
    return liste

1. Calculer la complexité de ce programme.
2. Quel est son ordre de grandeur ?