À propos de complexité

On a vu dans le cours la notion de complexité algorithmique. C'est une notion théorique, dans le sens où elle se calcule sur le papier, avec un stylo et sans ordinateur.

Cependant, afin de se familiariser avec cette notion de complexité, on va essayer dans ce TD de contrôler en visualisant informatiquement le résultat déterminé par le raisonnement.

On rappelle que le but est principalement d'estimer le nombre asymptotique (c'est à dire lorsque la taille des données devient grande) de passages successifs dans une boucle.

On rappelle enfin que si $T(n)$ est le nombre d'opérations élémentaires effectuées par un certain algorithme traitant des données de taille $n$, dire que la complexité de cet algorithme est en $O(f(n))$ signifie que lorsque $n$ devient grand, la suite $u_n=\dfrac{T(n)}{f(n)}$ est bornée.

L'objectif est donc dans chaque cas, de tracer la suite $u_n=\dfrac{T(n)}{f(n)}$ pour des valeurs de $n$ entre 1 et 1000 et de contrôler le caractère bornée de celle-ci.

Remarque : on ne s'intéressera pas ici aux résultats des divers algorithmes, ni à leur correction, mais uniquement à leur complexité.

I. Préliminaires

Afin de préparer le travail on va mettre en place quelques préliminaires.

Q1. Créer par compréhension une liste, nommée liste_n qui contient les valeurs de $n$ comprises entre 50 et 1000 allant de 50 en 50.

 # à compléter

# on teste :
print(liste_n)

Q2. Écrire une fonction liste_alea(n : int) -> list qui reçoit un entier $n$ et qui renvoie une liste de taille $n$, dont les éléments sont des entiers choisis aléatoirement entre 1 et $n$.

from random import randint

def liste_alea(n : int) -> list :
    """ à compléter ... """
    return # à compléter

# test :
print(liste_alea(10))

II. Un algorithme linéaire, $O(n)$

On a vu dans le cours, que l'algorithme de recherche séquentielle d'un élément dans une liste, était linéaire dans le pire des cas. On rappelle cet algorithme :

def recherche_seq(S : list,x : int):
    i,n = 1,len(S)
    while i<n and x!=S[i]:
        i = i +1
    return i!=n

Q3. Compléter l'algorithme suivant en ajoutant une variable globale nommée compteur qui détermine le nombre total de passages dans la boucle.

def recherche_seq(S : list,x : int):
    # à compléter
    
    i,n = 1,len(S)
    # à compléter
    
    while i<n and x!=S[i]:
        i = i +1
        # à compléter
        
    return i!=n

# on teste :
compteur = 0
S = liste_alea(10)
recherche_seq(S,-1) # on cherche un élément qui n'est pas dans S (pire des cas)
print(f"Nombre de passages dans la boucle : {compteur}")

Q4. Écrire une fonction complexite_rech_seq(n : int) -> int:. Elle reçoit un entier $n$ et renvoie le nombre de passages effectués dans la boucle de la fonction recherche_seq(S,-1) où $S$ est une liste aléatoire de taille $n$ (on utilisera la variable globale compteur...)

def complexite_rech_seq(n) -> int :
    pass
    # à completer
    

# on teste :
print(complexite_rech_seq(100))

Q5. Étudier le code ci-dessous et expliquer pourquoi cela permet de confirmer que la complexité de l'algorithme de recherche séquentiel est bien linéaire.

import matplotlib.pyplot as plt

def f(n) : # complexité estimée
    return n

X = liste_n
Y = [complexite_rech_seq(n)/f(n) for n in X]

plt.plot(X,Y,marker='o')
plt.show()

Réponse : l'algorithme de recherche séquentielle semble bien être de complexité linéaire car ... à compléter...

III. Un algorithme quadratique, $O(n^2)$

On a vu dans le cours que le tri à bulles était quadratique. En s'inspirant de la partie précédente. On rappelle cet algorithme :

def tri_bulles(S):
    n = len(S)
    for i in range(n-1,1,-1):
        for j in range(0,i):
            if (S[j]>S[j+1]) :
                S[j], S[j+1] = S[j+1],S[j]
    return S

Q6. Compléter l'algorithme suivant en ajoutant une variable globale nommée compteur qui détermine le nombre total de passages dans la boucle.

def tri_bulles(S):
    n = len(S)
    # à compléter
    # à compléter
    for i in range(n-1,1,-1):
        for j in range(0,i):
            # à compléter
            if (S[j]>S[j+1]) :
                S[j], S[j+1] = S[j+1],S[j]
    return S

# on teste :
compteur = 0
S = liste_alea(10)
tri_bulles(S) # on trie la liste S
print(f"Nombre de passages dans la boucle : {compteur}")

Q7. Écrire une fonction complexite_tri_bulles(n int) -> int. Elle reçoit un entier $n$ et renvoie le nombre de passages effectués dans la boucle de la fonction tri_bulles(S) où $S$ est une liste aléatoire de taille $n$

def complexite_tri_bulles(n) -> int :
    pass
    # à completer
        

# on teste :
print(complexite_tri_bulles(100))

Q8. En s'inspirant de la partie précédente, écrire un code qui permet de vérifier visuellement que la complexité de cet algorithme de tri à bulle est bien de complexité quadratique (c'est à dire en $O(n^2)$).

import matplotlib.pyplot as plt

# à compléter

Conclusion : à compléter

IV. Un algorithme logarithmique, $O(\ln n)$

On verra (dans un prochain chapitre) que lorsque une liste est triée, on peut implémenter un algorithme de recherche dichotomique pour retrouver des éléments. Celui-ci est beaucoup plus efficace que celui de recherche séquentielle, car il est en $O(\ln n)$. On donne cet algorithme (ce n'est pas la peine de l'étudier en détail car on le retravaillera bientôt) :

def recherche_dichotomie(L : list, e : int) -> bool :
    a,b = 0,len(L)-1 # les indices gauche et droite
    while a<=b :
        m = (a+b)//2 # division entiere
        if e == L[m]:
            return True
        else :
            if e < L[m] :
                b = m-1
            else:
                a = m+1
    return False

Q9. Compléter l'algorithme suivant en ajoutant une variable globale nommée compteur qui détermine le nombre total de passages dans la boucle.

def recherche_dichotomie(L : list, e : int) -> bool :
    a,b = 0,len(L)-1 
    # à compléter
    # à compléter
    while a<=b :
        m = (a+b)//2 
        # à compléter
        if e == L[m]:
            return True
        else :
            if e < L[m] :
                b = m-1
            else:
                a = m+1
    return False

# on teste :
compteur = 0
S = list(range(10)) # attention la liste doit être triée
recherche_dichotomie(S,-1)  # on cherche un élément qui n'est pas dans S (pire des cas)
print(f"Nombre de passages dans la boucle : {compteur}")

Q10. Écrire une fonction complexite_rech_dic(n int) -> int. Elle reçoit un entier $n$ et renvoie le nombre de passages effectués dans la boucle de la fonction recherche_dichotomique(S,-1) où $S$ est une liste triée de taille $n$

def complexite_rech_dic(n) -> int :
    pass
    # à completer
    
    

# on teste :
print(complexite_rech_dic(100))

Q11. En s'inspirant de la partie précédente, écrire un code qui permet de vérifier visuellement que la complexité de cet algorithme de recherche par dichotomie est bien de complexité logarithmiQUE (c'est à dire en $O(\ln n)$).

import matplotlib.pyplot as plt
import math # on obtient ln(n) avec math.log(n)

# à compléter

Conclusion : à compléter