Coût☘

Lorsqu'on s'intéresse à l'efficacité d'un algorithme, on estime deux coûts:

Le coût en nombre d'opérations élémentaires (qui donne une estimation du temps nécessaire à l'exécution).
Le coût en mémoire.

Nous allons ici nous occuper uniquement du coût en nombre d'opérations.

Exercice 1☘

On considère le code suivant:

def max_bin(a,b):
    """
    a et b sont de même type, comparables.
    La fonction renvoie le plus grand des deux.
    """
    return a if a > b else b

def max_tableau(tab):
    """
    tab est une liste d'éléments de même type, comparables.
    La fonction renvoie la plus grande des valeurs de ces éléments.
    """
    m = tab[0]
    for x in tab:
        m = max_bin(m,x)
    return m

Combien d'appels à la fonction max_bin effectue-t-on lors d'une recherche de maximum sur une liste de longueur n?
Que pourrait-on en déduire sur le temps d'exécution de la fonction max_tableau?

Nombre d'appels

On appelle exactement n fois la fonction max_bin.

Conséquence sur le temps

La fonction max_bin a un nombre d'opérations constant et s'exécute donc en un temps t à peu près constant (dans la pratique, ce temps varie: cela dépend bien entendu de la machine sur lequel on exécute le code, mais sur une même machine, cela dépend également du nombre de processus en cours d'exécution).

A chaque tour de boucle, on a donc ce temps t d'exécution de la fonction max_bin plus le temps d'une affectation ( m ← ...), soit un temps T à chaque tour de boucle.

Le temps d'exécution de notre fonction de recherche du maximum est donc de n*T. Le coût est linéaire (la fonction $n \longmapsto nT$ est une fonction linéaire).

Exercice 2☘

Question 1☘

Comprendre le rôle des fonctions ci-dessous, ajouter leurs docstrings. Tester.

def distance( p, q):
    return ((q[0] - p[0])**2 + (q[1] - p[1])**2)**0.5



def indice_min_distance_tableau(tab, un_point):

    indice = 0
    distance_minimale = distance( un_point, tab[0])

    for j in range(1,len(tab)):
        dist = distance(  un_point, tab[j])
        if dist < distance_minimale:
            distance_minimale = dist
            indice = j

    return indice

Commentaires sur le script

def distance( p, q):
    """
    p = (x,y) couple des coordonnées d'un point
    q = (x',y') couple des coordonnées d'un point
    La fonction renvoie la distance de p à q 
    (distance euclidienne usuelle)
    """
    return ((q[0] - p[0])**2 + (q[1] - p[1])**2)**0.5



def indice_min_distance_tableau(tab, un_point):
    """
    tab est une liste de couples (x,y) couple des coordonnées de points.
    un_point est un couple de coordonnées d'un point.
    La fonction renvoie un indice de la liste 
    tel que le point associé à cet indice
    réalise la plus petite des distances 
    entre un_point et un point de la liste.
    """
    indice = 0
    distance_minimale = distance( un_point, tab[0])

    for j in range(1,len(tab)):
        dist = distance(  un_point, tab[j])
        if dist < distance_minimale:
            distance_minimale = dist
            indice = j

    return indice




# tests
from random import randint
L = [ (randint(-20,20), randint(-20,20)) for _ in range(randint(1,20))]
point = (0,0)
M = []
for x in L: M.append(distance(x, point))
print(L)
print(M)
k = indice_min_distance_tableau( L, point )
print(k)

Info

Nous reparlerons de ce problème des points les plus proches lorsque nous aborderons l'algorithme "des k plus proches voisins".

Question 2☘

Le programme précédent a-t-il un coût linéaire par rapport à la longueur de liste?

Info

On dira que le coût d'un algorithme est linéaire (ici en fonction de la longueur n de liste) si le nombre d'opérations élémentaires nécessaires à l'exécution de l'algorithme est compris entre deux fonctions affines de la variable n.

Dans cette définition, nous utilisons le terme "opération élémentaire", qu'il faudrait définir. Nous considérerons notamment dans ces opérations élémentaires:

les comparaisons de deux nombres
les affectations
les sommes, différences
les produits, divisions

Coût

Le coût en opérations élémentaires est une fonction linéaire de la variable n = longueur de la liste.

Précisons un peu cela.

def distance( p, q):
    """
    p = (x,y) couple des coordonnées d'un point
    q = (x',y') couple des coordonnées d'un point
    La fonction renvoie la distance de p à q 
    (distance euclidienne usuelle)
    """
    return ((q[0] - p[0])**2 + (q[1] - p[1])**2)**0.5


def indice_min_distance_tableau(tab, un_point):
    """
    tab est une liste de couples (x,y) couple des coordonnées de points.
    un_point est un couple de coordonnées d'un point.
    La fonction renvoie un indice de la liste 
    tel que le point associé à cet indice
    réalise la plus petite des distances 
    entre un_point et un point de la liste.
    """
    indice = 0
    distance_minimale = distance( un_point, tab[0])

    for j in range(1,len(tab)):
        dist = distance(  un_point, tab[j])
        if dist < distance_minimale:
            distance_minimale = dist
            indice = j

    return indice

Comptons d'abord les comparaisons (utilisation de <). Il y a une comparaison à chaque tour de boucle (dans le if). Il y a donc n-1 comparaisons (où n est la longueur de liste). Si chaque comparaison demande un temps constant $t_{comparaison}$ , on a donc un temps de $(n-1)t_{comparaison}$ .
Comptons maintenant les affectations.
- il y en a une en ligne 21.
- Une affectation en ligne 24 à chaque tour de boucle, donc n-1 affectations.
- L'affectation de la ligne 26 est effectuée entre 0 (cas où la condtion du if est toujours à False) et n-1 fois (cas où la condition du if est toujours à True).
- Idem en ligne 27.
Le nombre d'affectations est donc compris entre n + 0 et n + 2(n-1). Si une affectation demande un temps constant $t_{affectation}$ , on a donc un temps compris entre $n\times t_{affectation}$ et $(3n-2)\times t_{affectation}$ .
On ajoute n-1 appels à la fonction distance en ligne 21. La fonction distance s'exécute en un temps constant $t_{distance}$ (calcul de la distance). D'où un temps de $(n-1)t_{distance}$ .

Nous avons donc pour le moment, un temps compris entre $(n-1)t_{comparaison} + n\times t_{affectation} + (n-1)t_{distance}$ et $(n-1)t_{comparaison} + (3n-2)\times t_{affectation} + (n-1)t_{distance}$ .

Si pour simplifier, nous considérons que tous ces temps sont à peu identiques (temps T) (c'est un abus, mais on considérera qu'à notre 'échelle', on peut commettre cet abus), nous voyons que le temps est compris entre $(3n-2)T$ $(5n-4)T$ , c'st à dire entre deux fonctions affines (variable n).

Si nous voulons être complet, il faudrait ajouter par exemple les temps d'accès à un élément de liste (tab[j])... mais peu importe, l'essentiel est là: le nombre d'opérations élémentaires est compris entre deux fonctions affines, c'est cela qui est qualifié de "coût linéaire".

Question 3☘

Ecrivez maintenant un corps possible pour la fonction python ci-dessous:

def distance( p, q):
    """
    p = (x,y) couple des coordonnées d'un point
    q = (x',y') couple des coordonnées d'un point
    La fonction renvoie la distance de p à q
    """
    return ((q[0] - p[0])**2 + (q[1] - p[1])**2)**0.5




def les_indices_des_deux_points_les_plus_proches(tab):
    """
    tab est une liste de couples (x,y) couple des coordonnées de points.
    La fonction renvoie les indices des deux points les plus proches dans ce tableau.
    """

Un code possible

Un code possible:

def distance( p, q):
    """
    p = (x,y) couple des coordonnées d'un point
    q = (x',y') couple des coordonnées d'un point
    La fonction renvoie la distance de p à q
    """
    return ((q[0] - p[0])**2 + (q[1] - p[1])**2)**0.5




def les_indices_des_deux_points_les_plus_proches(tab):
    """
    tab est une liste de couples (x,y) couple des coordonnées de points.
    La fonction renvoie les indices des deux points les plus proches dans ce tableau.
    """

    indice1, indice2 = 0, 1
    distance_minimale = distance( tab[indice1], tab[indice2])

    for i  in range(len(tab)-1):
        for j  in range(i+1,len(tab)):
            dist = distance( tab[i], tab[j])
            if dist < distance_minimale:
                distance_minimale = dist
                indice1, indice2 = i, j

    return indice1, indice2

# tests
from random import randint
L = [ (randint(-20,20), randint(-20,20)) for _ in range(randint(1,20))]

print(L)
i, j = les_indices_des_deux_points_les_plus_proches(L)

print(i, j)

Question 4☘

Le programme précédent a-t-il encore un coût en temps linéaire par rapport à la longueur de liste?

Une réponse

La réponse est non.

Dans le corps de boucle:

dist = distance( tab[i], tab[j])
if dist < distance_minimale:
    distance_minimale = dist
    indice1, indice2 = i, j

On effectue une comparaison, entre 1 et 3 affectations, une exécution de la fonction distance (qui fait toujours intervenir le même nombre d'opérations). Notons $n_1$ le nombre d'opérations élémentaires lorsque la condition du if est à False et $n_2$ le nombre d'opérations élémentaires lorsqu'elle vaut True. Soit $f(n)$ le nombre d'exécutions de ce corps de boucle. Le nombre d'opérations élémentaires est compris entre $n_1\times f(n)$ et $n_2\times f(n)$ .

La question est maintenant de déterminer $f(n)$ . Le nombre d'exécutions du corps de boucle:

1
2
3

for i  in range(len(tab)-1):
    for j  in range(i+1,len(tab)):
        corps

Pour chaque valeur de i (i entre 0 et n-2), la boucle est exécutée n-i-1 fois. Le nombre d'exécutions de la boucle est donc: (n-0-1)+(n-1-1)+(n-2-1)+(n-3-1)+...+(n-(n-2)-1) = (n-1)+(n-2)+(n-3)+...+1

Pour déterminer cette somme, on peut utiliser l'astuce suivante:

D'où l'on déduit que $2S = n \times (n-1)$ ou encore $S = \frac{1}{2} n^2 - \frac{1}{2} n$ .

La fonction f n'est pas affine: c'est une fonction du second degré.

Info

Lorsque le coût en opérations est compris entre deux fonctions du second degré, on dit que le coût est quadratique.