Exercices de complexité

Reading time2h30

Consignes globales

Résumé de l’article

Dans cette partie, nous vous proposons de travailler sur l’analyse de plusieurs fonctions, allant de structures simples à des processus récursifs plus complexes. Le but sera de dérouler les algorithmes pour comprendre ce qu’ils font et d’analyser la complexité qui en découle. Cet atelier pratique sera à faire sur papier sans utiliser un ordinateur donnant les réponses.

Une fois tous les exercices réalisés, vous pourrez utiliser le code donné dans le cours pour comparer les complexités temporelles et spatiales en python. Puis à nouveau sur papier, vous pourrez essayer de trouver pour chaque fonction des versions améliorant la complexité temporelle ou spatiale.

Contenu de l’activité

Complexité de fct1

Quelles sont les complexités temporelle et spatiale dans le pire des cas de l’algorithme suivant ? Justifiez votre réponse.

1def fct1 (m: int, n: int):
2    for i in range(m) :
3        for j in range(n) :
4            print("X", end=',')
5        print()

Complexité de fct2_1 et fct2_2

Quelles sont les complexités temporelle et spatiale dans le pire des cas de l’algorithme fct2_1 ? Justifiez votre réponse.

1def fct2_1 (n: int):    
2    nombres = [i for i in range (1, n+1)]
3    return sum(nombres)

Et maintenant donnez celles de l’algorithme fct2_2 ? Justifiez votre réponse.

1def fct2_2 (n: int):
2
3    # Déclaration d'une variable entière initialisée à 0
4    s = 0
5    for i in range(1, n+1):
6        s += i
7    return s

Complexité de fct3

Quelles sont les complexités temporelle et spatiale dans le pire des cas de l’algorithme fct3 ? Justifiez votre réponse.

 1def fct3 (m: int, n: int):
 2
 3    # Déclaration de deux variables entières initialisées à 1
 4    i = 1
 5    j = 1
 6
 7    while (j <= n):
 8        if i <= m:
 9            i = i+1
10        else 
11            j = j+1
12        print("X")

Complexité de fct4

Quelles sont les complexités temporelle et spatiale dans le pire des cas de l’algorithme fct4 ? Justifiez votre réponse.

1def fct4 (T : list[int]):
2    for i in range(len(T)):
3        for j in range(len(T)):
4            print(T[i] + T[j])

Complexité de product_matrix

Quelles sont les complexités temporelle et spatiale dans le pire des cas de l’algorithme product_matrix ? Justifiez votre réponse.

1def product_matrix (A : list[list[int]], B : list[list[int]]):
2    n = len(A)
3    C = [[0] * n for _ in range(n)]
4    for i in range(n):
5        for j in range(n):
6            for k in range(n):
7                C[i][j] += A[i][k] * B[k][j]
8    return C

Complexité de somme_diviser

Quelles sont les complexités temporelle et spatiale dans le pire des cas de l’algorithme somme_diviser ? Justifiez votre réponse.

1def somme_diviser(T: list[int]): # T de taille n
2    if len(T) <= 1:
3        return sum(T)
4    mid = len(T) // 2
5    gauche = somme_diviser(T[:mid])
6    droite = somme_diviser(T[mid:])
7    return gauche + droite

Complexité de somme_sous_ensembles

Quelles sont les complexités temporelle et spatiale dans le pire des cas de l’algorithme somme_sous_ensembles ? Justifiez votre réponse.

1def somme_sous_ensembles(T: list[int], i: int = 0, courant: int = 0) : # T de taille n
2    """Affiche toutes les sommes possibles de sous-ensembles de T."""
3    if i == len(T):
4        print(courant)
5        return
6    somme_sous_ensembles(T, i + 1, courant)         
7    somme_sous_ensembles(T, i + 1, courant + T[i])

Que deviennent ces complexités si au lieu d’afficher les sommes, nous voulons les stocker dans une variable globale res de type list ? (Au lieu de print(courant), nous aurions res.append(courant))

Analyse de fct5

  1. Déterminez ce que fait l’algorithme fct5. Puis donnez les complexités temporelle et spatiale dans le pire des cas de l’algorithme en justifiant votre réponse.
 1def fct5(n: int, m: int) :
 2    i = 1
 3    j = 1
 4    res = ""
 5    while j <= m:
 6        res += f"{j} {i}\n"
 7        if i < n:
 8            i += 1
 9        else:
10            j += 1
11            i = 1
12    return res
  1. Re-écrivez l’algorithme fct5 de manière plus lisible (le résultat reste le même).

Complexité d’une suite récurrente

Soit la suite $U_i$ définie par :

  • $U_0=1$
  • $U_i=2*U_{i-1}+(U_{i-1}*U_{i-1})$ si $i>0$

Ecrire une fonction récursive $u_i$ qui si $i\geq 0$ retourne la valeur de $U_i$. Etudier la complexité temporelle et spatiale dans le pire des cas de votre implémentation. Proposez des versions différentes en améliorant au mieux votre code.

Analyse de fct6

  1. Déterminez ce que fait l’algorithme fct6. Puis donnez les complexités temporelle et spatiale dans le pire des cas de l’algorithme en justifiant votre réponse.
1def fct6(t : list[int]):
2    n = len(t)
3    for i in range(n - 1):
4        for j in range(n - 1):
5            if t[j] > t[j + 1]:
6                temp = t[j]
7                t[j] = t[j + 1]
8                t[j + 1] = temp
9
  1. Que se passe-t-il dans le meilleur cas ? Améliorez l’algorithme en réduisant le nombre de pas de boucles inutiles pour i. Quelles sont les nouvelles complexités ?
  1. Que remarquez vous sur la boucle interne parcourue par j à chaque incrémentation de i ? Améliorez l’algorithme en réduisant le nombre de pas de boucles inutiles pour j. Quelles sont les nouvelles complexités ?