Exercices de complexité

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 fait, 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 des versions plus optimisées de chaque algorithme.

- Exercice 1

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

def fct1 (m: int, n: int):

    # Déclaration de deux variables entières initialisées à 1
    for i in range(m):
        for j in range(n):
            print("X", end=",")
        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.

def fct2_1 (n: int):

    # Déclaration d'une variable entière initialisées à 0
    nombres = [i for i in range (1, n+1)]
    return sum(nombres)

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

def fct2_2 (n: int):

    # Déclaration d'une variable entière initialisées à 0
    s = 0
    
    for i in range(1, n+1):
        s += i
    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.

def fct3 (m: int, n: int):

    # Déclaration de deux variables entières initialisées à 1
    i = 1
    j = 1

    while (j <= n):
        if i <= m:
            i = i+1
        else 
            j = j+1
        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.

def fct4 (T : List[int]):
    for i in range(len(T)):
        for j in range(len(T)):
            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.

def product_matrix (A : List[List[int]],B : List[List[int]]):
    n = len(A)
    C = [[0] * n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            for k in range(n):
            C[i][j] += A[i][k] + B[k][j]

- Exercice 6

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

def somme_diviser(T[n]):
    if len(T) <= 1:
        return sum(T)
    mid = len(T) // 2
    gauche = somme_diviser(T[:mid])
    droite = somme_diviser(T[mid:])
    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.

def somme_sous_ensembles(T[n], i: int = 0, courant: int = 0) :
    """Affiche toutes les sommes possibles de sous-ensembles de T."""
    if i == len(T):
        print(courant)
        return
    somme_sous_ensembles(T, i + 1, courant)         
    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 fact5. Puis donnez les complexités temporelle et spatiale dans le pire des cas de l’algorithme en justifiant votre réponse.

def fct5(n: int, m: int) :
    i = 1
    j = 1
    res = ""
    while j <= m:
        res += f"{j} {i}\n"
        if i < n:
            i ++
        else:
            j ++
            i = 1
    return res

Re-écrivez l’algorithme fact5 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 fact6. Puis donnez les complexités temporelle et spatiale dans le pire des cas de l’algorithme en justifiant votre réponse.

def fct6(t : List[int]):
    n = len(t)
    for i in range(n - 1):
        for j in range(n - 1):
            if t[j] > t[j + 1]:
                temp = t[j]
                t[j] = t[j + 1]
                t[j + 1] = temp

Que se passe t’il dans le meilleur cas ? Améliorez l’algorithme en réduisant le nombre de pas de boucles inutile pour i. Quelles sont les nouvelles complexités ?
Que remarquez vous sur la boucle interne faite par j à chaque incrémentation de i ? Améliorez l’algorithme en réduisant le nombre de pas de boucles inutile pour j. Quelles sont les nouvelles complexités ?