Étude de complexité

Soient i et j deux entiers, b1 et b2 deux booléens, tab est un tableau, l une liste, a un arbre. On s'intéresse au nombre d'opérations élémentaires réalisées par un algorithme (son "coût"). Pour cela, on prendra les conventions suivantes :

Instruction	Coût
i + j	1
i - j	1
i*j	1
i/j	1
i = j=	1
i < j	1
i > j	1

Instruction	Coût
b1 and b2	0
b1 or b2	0
not b1	0
Affectation	0
return	0
tab[i]	0
if, elif, else	0

Instruction	Coût
creer_vide()	0
est_vide()	0
tete(l)	0
queue(l)	0
ajoute(l, i)	1
gauche(a)	0
droit(a)	0
etiquette(a)	0
Arbre(i, sag, sad)	1

Complexité d'une fonction itérative

1. On considère le code python suivant :

   def puissance(x, n):
       """ int, int -> int
       Renvoie x^n """       
       res = 1
       for i in range(n):
           res = res*n
       return res 
   

   1. Lors de l'exécution de l'instruction puissance(2, 15), combien de fois la ligne 6 est-elle exécutée ?

   2. En déduire le coût de la fonction puissance en fonction de x et n.

2. 1. Écrire une fonction minimum qui étant donné un tableau tab, en renvoie le plus petit élément ainsi que son indice.

   2. Exprimer en fonction de tab le nombre d'opérations effectuées par la fonction minimum.

3. On rappelle le code de la fonction tri_selection. Celle-ci prend en entrée un tableau tab et le trie en place. Ainsi, la dernière ligne du code ci-dessous est facultative. On admettra que l'instruction mini_a_partir(tab, i) réalise len(tab) - i opérations.

   def tri_selection_iter(tab):
       """ [int] -> [int]
       Trie le tableau tab, qui peut être modifié. """
       for i in range(len(tab)):
           indice_mini = mini_a_partir(tab, i)
           tab[i], tab[indice_mini] = tab[indice_mini], tab[i]
       return tab
   

   1. On note \(n\) le nombre len(tab). Expliquer pourquoi le nombre d'opérations réalisés par l'instruction tri_selection_iter(tab) est :

      \(n + (n-1) + (n-2) + \ldots + 2 + 1 \)

   2. En déduire le nombre d'opérations réalisés par l'instruction tri_selection_iter(tab).

Complexité d'une fonction récursive

Dans cet exercice, étudie la complexité de la fonction longueur (pour une liste). Si l est une liste constituée de \(n\) éléments, on note \(c_n\) le nombre d'opérations effectuées par longueur(l). On donne ci-dessous le code de la fonction longueur, où chaque ligne ne contient qu'un seul appel de fonction.

def longueur(l):
    if est_vide(l):
        return 0
    else:
        reste = queue(l)
        long_queue = longueur(reste)
        total = 1 + longueur_queue
        return total

1. 1. Si \(l\) est la liste vide, quelle(s) ligne(s) de la fonction longueur sont exécutées ? Combien cela représente-t-il d'opérations ? En déduire la valeur de \(c_0\).

   2. Si \(l = (42)\), quelle(s) ligne(s) de la fonction longueur sont exécutées ? Combien cela représente-t-il d'opérations ? En déduire la valeur de \(c_1\).

2. 1. Si \(l\) est une liste constituée de \(n\) éléments, quelle(s) ligne(s) de la fonction longueur seront exécutées ? Compléter le tableau de l'énoncé.

   2. Pour tout \(n \geq 1\), exprimer \(c_n\) en fonction de \(c_{n - 1}\).

      Quelle est la nature de la suite \((c_n)_{n \geq 0}\) ?

   3. Pour tout \(n \geq 0\), exprimer \(c_n\) en fonction de \(n\).

Influence du cas de base

Dans cet exercice, on étudie la complexité de la fonction maximum (pour une liste). Si l est une liste constituée de \(n\) éléments, alors on note \(c_n\) le nombre d'opération effectuées par l'instruction maximum(l). La fonction maximum fait appel à la fonction maximum2 qui prend en entrée deux entiers a et b et renvoie le plus grand des deux.

def maximum(l):
    n = longueur(l)
    if n == 1:
        return tete(l)
    else:
        premier = tete(l)
        reste = queue(l)
        plus_grand_reste = maximum(reste)
        return maximum2(premier, plus_grand_reste)

1. Proposer le code d'une fonction maximum2. Combien d'opérations élémentaires votre fonction réalise-t-elle ?

2. 1. Si \(l\) est la liste constituée d'un seul élément, quelle(s) ligne(s) de la fonction maximum sont exécutées ? Combien cela représente-t-il d'opérations ? En déduire la valeur de \(c_1\).

   2. Si \(l\) est une liste constituée de \(n\) éléments, quelle(s) ligne(s) de la fonction maximum sont exécutées ? En déduire l'expression de \(c_n\) en fonction de \(c_{n - 1}\).

   3. Démontrer que pour tout \(n \geq 1\), \(c_n = \frac{n^2 + 5n - 2}{2}\).

3. Donner le code d'une fonction python mon_maximum qui étant donné une liste l en renvoie le plus grand élément, avec une complexité linéaire en la taille de l.

   Justifier que la complexité est alors linéaire.

Complexité dans le pire des cas

Dans cet exercice on compare les complexités des deux fonctions appartient, dont on donne le code ci-dessous. Elles prennent toutes deux en entrée une liste l et un entier e, et déterminent si l'entier e est présent dans la liste l.

def appartient1(l, e):
 if est_vide(l):
  return False
 else:
  est_tete = (tete(l) == e)
  reste = queue(l)
  dans_queue = appartient1(reste, e)
  reponse = (est_tete or dans_queue)
  return reponse

def appartient2(l, e):
 if est_vide(l):
  return False
 else:
  if tete(l) == e:
   return True
  else:
   reste = queue(l)
   return appartient2(reste, e)

1. Si \(n\) est le nombre d'éléments de l, on note \(c_n\) le nombre d'opérations réalisées par appartient1(l, e)

   Exprimer \(c_n\) en fonction de \(n\), pour tout \(n \geq 0\).

2. 1. Soit la liste \(l = (5, 8, 4, 6, 16)\). 1. On exécute l'instruction appartient2(l, 5). Quelles lignes de la fonction appartient2 seront-elles exécutées ? Combien cela représente-t-il d'opérations ?

      1. On exécute l'instruction appartient2(l, 4). Combien cela représente-t-il d'opération ? Aucune justification n'est attendue.

      2. On exécute l'instruction appartient2(l, 42). Combien cela représente-t-il d'opération ? Aucune justification n'est attendue.

      3. Dans quel cas l'instruction appartient2(l, e) effectue-t-elle le plus d'opérations ?

   2. On note \(d_n\) le nombre d'opérations réalisées par appartient2 dans le pire des cas.

      Pour tout \(n \geq 1\), exprimer \(d_n\) en fonction de \(d_{n - 1}\), puis en déduire l'expression de \(d_n\) en fonction de \(n\).

Complexité et arbres

On dit qu'un arbre binaire est parfait lorsque toutes ses feuilles ont la même profondeur. Il s'agit donc d'un arbre binaire dont tous les niveaux sont remplis. Dans cet exercice, a sera toujours un arbre binaire parfait, \(n\) est le nombre de nœuds de a et \(h\) est sa hauteur (avec la convention que l'arbre constitué d'un élément a une hauteur de 0).

1. Exprimer \(n\) en fonction de \(h\). En déduire l'expression de \(h\) en fonction de \(n\).

2. On donne ci-dessous le code de la fonction taille. Elle prend en entrée un arbre binaire parfait a et en renvoie le nombre de nœuds qui le composent.

   On s'intéresse à la complexité de cette fonction. On note \(c_h\) le nombre d'opérations effectuées par taille(a) lorsque a a pour hauteur \(h\).

   def taille(a):
       if est_vide(a):
           return 0
       else:
           n_sag = taille(gauche(a))
            n_sad = taille(droit(a))
            n_tot = 1 + n_sag + n_sad
            return n_tot
   

   1. Déterminer \(c_0\), \(c_1\), \(c_2\).

   2. Pour tout \(h \geq 1\), exprimer \(c_h\) en fonction de \(c_{h - 1}\).

   3. Démontrer que pour tout \(h \geq 0\),

      \(c_h = 2^{h + 1} - 2\)

   4. Combien l'intruction taille(a) réalise-t-elle d'opérations lorsque l'arbre a comporte \(n = 63\) nœuds ?

Arbres vs arbre binaire de recherche

Dans cet exercice on compare les complexités des deux fonctions appartient, dont on donne le code ci-dessous. Elles prennent toutes deux en entrée un arbre binaire parfait a de taille \(n\) et de hauteur \(h\), un entier e, et déterminent si l'entier e est présent dans l'arbre a.

def appartient1(a, e):
 if est_vide(a):
  return False
 else:
  ds_sag = appartient1(gauche(a), e)
  ds_sad = appartient1(droit(a), e)
  est_racine = (racine(a) == e)
  return est_racine or ds_sag or ds_sad

def appartient2(a, e):
 if est_vide(a):
  return False
 else:
  if e <racine(a):
   dans_sag = appartient2(gauche(a), e)
   return dans_sag
  elif e > racine(a):
   dans_sad = appartient2(droit(a), e)
   return dans_sad
  else:
   return True

1. Pour \(h > 0\), on note \(c_h\) le nombre d'opérations effectuées par la fonction appartient1, lorsque a est un arbre binaire parfait de hauteur \(h\).

   Démontrer que \(c_h = 2^h - 1\).

2. 1. Quelle propriété doit vérifier l'arbre a pour que la fonction appartient2 détermine correctement si l'arbre a contient l'élément e ?

   2. Combien d'appels récursifs au maximum réalise-t-on lors de l'exécution de l'instruction appartient2(a, e) ?

   3. On note \(d_{h}\) le nombre d'opérations réalisées par appartient2(a, e) dans le pire des cas lorsque a est un arbre binaire parfait de hauteur \(h\).

      Déduire des questions précédentes que \(d_h = 2h\).

Relations de récurrences et complexité

Soit f une fonction à un argument, de "taille" n.

On note \(c_n\) le nombre d'opérations effectuées par f(n).

1. Associer chacune des équations ci-dessous à son comportement asymptotique.

   

2. À quelles complexités correspondent chacun des algorithmes ci-dessous ?

   • la recherche d'un élément dans une liste dans le pire des cas

   • la recherche d'un élément dans un arbre binaire

   • la recherche d'un élément dans un arbre binaire de recherche

   • la résolution du problème de Hanoï à \(n\) disques

   • le tri par séléction (implémentation itérative)

   • le tri fusion