Analyser la complexité du code avec Python

La complexité d’un algorithme mesure la quantité de temps et/ou d’espace nécessaire à son exécution pour une entrée de taille donnée (n). La complexité d’un algorithme dépend de facteurs spécifiques tels que : l’architecture de l’ordinateur (c’est-à-dire la plateforme matérielle), la représentation du type abstrait de données (ADT), l’efficacité du compilateur, la complexité de l’algorithme sous-jacent et la taille de l’entrée. Les facteurs les plus déterminants restent toutefois la complexité de l’algorithme sous-jacent et la taille de l’entrée.

Dans l’article du blog DataCamp Python Data Structures Tutorial, vous trouverez une vue d’ensemble des structures de données et leur implémentation en Python. Ce billet introduit les structures de données de base de Python. Vous y découvrirez les types abstraits de données et les structures de données, les structures primitives et non primitives.

Analyse asymptotique

L’analyse asymptotique consiste à mesurer le temps d’exécution d’un morceau de code ou d’une opération en unités mathématiques de calcul. Les opérations sont exprimées en fonction d’une fonction f(n). En analyse mathématique, l’asymptotique est une méthode qui décrit le comportement limite.

Le temps requis par un algorithme se décline en trois cas : Pire cas – le temps maximal requis par un algorithme, le plus couramment utilisé lors de l’analyse. Meilleur cas – le temps minimal requis par l’algorithme, rarement calculé. Cas moyen – le temps moyen requis par un algorithme, parfois étudié.

Notation asymptotique

Les notations les plus utilisées pour estimer la complexité temporelle d’un algorithme sont :

• notation Big O
• notation Big θ
• notation Big Ω

Notation Big O, Ο

Big O sert à mesurer les performances ou la complexité d’un algorithme. En termes mathématiques, c’est une borne supérieure du taux de croissance d’une fonction : si une fonction g(x) ne croît pas plus vite qu’une fonction f(x), alors g appartient à O(f). De manière générale, elle exprime la borne supérieure d’un algorithme et fournit une mesure de son pire temps d’exécution, c’est-à-dire la durée maximale possible pour terminer.

Notation Big Omega, Ω

La notation Ω(n) exprime formellement la borne inférieure du temps d’exécution d’un algorithme. Elle mesure le meilleur cas, c’est-à-dire la durée minimale pour terminer.

Notation Big Theta, θ

La notation θ(n) exprime formellement à la fois la borne inférieure et la borne supérieure du temps d’exécution d’un algorithme.

La notation sert à déterminer la complexité de différents algorithmes

La notation Big O est de loin la plus utilisée pour trouver la borne supérieure d’un algorithme, tandis que la notation Big θ sert parfois à caractériser le cas moyen, et la notation Ω est la moins utilisée des trois.

Vous trouverez ci-dessous des exemples de notations appliquées à des algorithmes pour déterminer leur complexité.

Par exemple, pour le tri rapide :

Quick sort est un algorithme « diviser pour régner » utilisé pour trier. Il fournit une méthode systématique pour mettre des éléments en ordre, par exemple trier un tableau de nombres par ordre croissant ou décroissant. L’algorithme choisit un pivot, c’est-à-dire un indice sélectionné dans le tableau. Le pivot peut être choisi de différentes manières. Dans l’exemple ci-dessous, on choisit comme pivot le dernier élément.

Le cœur de Quick sort est la partition. À partir d’un tableau, on choisit un élément de partition, on le place à sa position correcte, puis on place les éléments supérieurs à droite du pivot et les éléments inférieurs à gauche.

#The last element will be taken as a pivot by the use of the function
#The smaller element is placed left to the pivot
#The greater element is placed to the right of the pivot
def partition(array,low,high):
    i = ( low-1 )         # index of smaller element is chosen
    pivot = array[high]     # pivot is chosen

    for j in range(low , high):

        #Is the element less or equal to the pivot
        if   array[j] <= pivot:

            # increment index of smaller element
            i = i+1
            array[i],array[j] = array[j],array[i]

    array[i+1],array[high] = array[high],array[i+1]
    return ( i+1 )

# The main crux of the problem that implements Quick sort is
#array[] is to be sorted
#high is the ending index
#low is the starting index

# Function to do Quick sort
def quickSort(array,low,high):
    if low < high:

       #pit is the partitioning index
        pit = partition(array,low,high)

      #Element sorted before and after partition
        quickSort(array, low, pit-1)
        quickSort(array, pit+1, high)

array=[2,4,6,8,10,12]
n = len(array)
quickSort(array,0,n-1)
print ("The Sorted array is:")
for i in range(n):
    print ("%d" %array[i]),

The Sorted array is:
2
4
6
8
10
12
Vous obtiendrez la sortie :

The Sorted array is: 2 4 6 8 10 12

Passons maintenant à l’analyse de la complexité temporelle. Pour commencer :

• Meilleur cas : Ω(n log(n))
• Cas moyen : Θ(n log(n))
• Pire cas : O(n^2)

Analysons le code ci-dessus.

Meilleur cas : c’est le cas où l’élément de partition choisit un pivot au milieu. L’algorithme s’appelle alors récursivement sur la première et la seconde moitié. Le nombre total d’étapes nécessaires correspond au nombre de divisions par 2 pour passer de n à 1. Ainsi, n/2/2/2/.../2 = 1 en k étapes, soit n / 2^k = 1. Comme 2^log n = n, on obtient k = log n. Le nombre d’itérations est donc O(log n), et comme chaque itération coûte O(n), la complexité est O(n log n).

Cas moyen : pour le cas moyen, il faut considérer toutes les permutations du tableau et calculer le temps pour chacune. Vous pouvez en lire davantage sur Merge sort.

Pire cas : dans le pire cas, si le premier élément est choisi comme pivot, et que l’entrée est déjà triée (croissante ou décroissante), après la partition on obtient une partie de taille 1 et l’autre de taille n-1. Soit T(n) la fonction de temps : le temps de partitionner n éléments est O(n), plus le temps de trier récursivement n-1 éléments, T(n-1). Donc T(n) = T(n-1) + O(n) ⇒ T(n) = O(n^2).

Exemples

Le code ci-dessous est très simple : vous ne le qualifierez peut-être pas d’algorithme, mais techniquement, tout code qui accomplit une tâche est un algorithme, c’est une manière de résoudre un problème précis. L’exemple suivant utilise une boucle for contenant une seule instruction d’affichage.

print('I love Python');

Hello world !
La complexité temporelle de l’algorithme ci-dessus est O(1) car il ne prend qu’une seule étape : c’est un temps constant.

stuffs= ['eggs','toothbrush','kittens','mugs']
for stuff in stuffs:
    print("Here's a stuff: {}".format(stuff));

Here's a stuff: eggs Here's a stuff: toothbrush Here's a stuff: kittens Here's a stuff: mugs Comment qualifieriez-vous l’efficacité de l’algorithme ci-dessus en notation Big O ?

Pour l’analyser, il faut compter le nombre d’étapes. Ici, la liste contient quatre éléments, et vous affichez chacun une fois. Mais si la liste contenait 15 éléments, la boucle for prendrait-elle le même nombre d’étapes ? Comme cette boucle effectue autant d’étapes qu’il y a d’éléments, on dira que l’algorithme a une efficacité O(N), et non O(1).

L’exemple suivant est un petit algorithme Python qui détermine si un nombre est premier :

def is_prime(number):   
    for i in range(2, number):       
        if number % 2 == 0:           
            return True   
    return False

Le code ci-dessus accepte un nombre en argument et lance une boucle for qui divise par tous les nombres de 2 jusqu’à ce nombre pour vérifier le reste. S’il n’y a pas de reste, le nombre n’est pas premier et la fonction renvoie immédiatement False. Si vous atteignez le nombre en trouvant toujours un reste, alors le nombre est premier et vous renvoyez True.

On peut estimer l’efficacité de cet algorithme à O(N). Ici, l’entrée n’est pas un tableau ou une liste, mais un entier passé en argument. Si vous passez un nombre comme 11, la boucle s’exécute environ onze étapes (en réalité neuf, puisqu’elle commence à 2 et s’arrête juste avant le nombre). Pour 101, environ 101 étapes. Comme le nombre d’étapes croît de concert avec la valeur passée à la fonction, c’est un exemple classique de O(N).

def twoForLoops(n):
    for i in range(1,n):
        print("Printing:"+i);
    for i in range(1,100):
        print("Printing:"+i);

Dans le code ci-dessus, la complexité est O(N). Le second parcours sur 100 itérations peut être ignoré dans l’analyse asymptotique, car on suppose N très grand.

def twoConditionalLoops(m,n):
    for i in range(0,m):
        print("Printing:"+i);
    for i in range(0,n):
        print("Printing:"+i);

On a deux boucles : l’une de longueur m, l’autre de longueur n. En supposant m et n grands, la complexité est O(n + m). Les boucles étant indépendantes et recevant des entrées différentes, la complexité est additive.

def twoNestedForLoops(int m,int n):
    for i in range(0,n):
        for j in range(0,m):
            print("Printing:"+(i*j));

Ici, les boucles sont imbriquées. En supposant n et m grands, la complexité est O(n * m). Les boucles étant identiques et imbriquées, la complexité est multiplicative.

Bravo !

Vous êtes arrivé au bout de ce tutoriel ! Vous avez découvert les notations asymptotiques, un outil de base des programmeurs et des data scientists. Nous avons volontairement privilégié une explication simple, sans formalisme mathématique poussé. Même si les sujets « structures de données et algorithmes » sont souvent abordés dans les cursus d’informatique, il est utile d’en connaître les fondamentaux, sans viser l’expertise. Pour aller plus loin, consultez ce cours : MIT opencourseware Algorithm course

Si vous souhaitez en apprendre davantage sur Python, découvrez ces cours DataCamp :