Exercices de complexité

Reading time2h30

En bref

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.

- Exercice 1

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()

- Exercice 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

- Exercice 3

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")

- Exercice 4

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])

- Exercice 5

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

- Exercice 6

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

- Exercice 7

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))

- Exercice 8

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

Re-écrivez l’algorithme fct5 de manière plus lisible (le résultat reste le même).

- Exercice 9

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.

- Exercice 10

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

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 ?
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 ?