Exercices de complexité

• Complexité temporelle : $O(n*m)$
• Complexité spatiale : $O(1)$ Si au lieu d’afficher, nous stockions ‘X’ dans une liste, la complexité spatiale serait également de $O(n*m)$

• Complexité temporelle : $O(n)$
• Complexité spatiale auxiliaire : $O(n)$, liste créée avec la variable nombre. Mais ce stokage est inutile, comme on peut le voir avec fct2_2

• Complexité temporelle : $O(n)$
• Complexité spatiale : $O(1)$

• Complexité temporelle : $O(n+m)$
• Complexité spatiale : $O(1)$

• Complexité temporelle : $O(n^2)$
• Complexité spatiale en entrée : $O(n)$ pour la liste T
• Complexité spatiale auxiliaire : $O(1)$
• Donc complexité spatiale totale : $O(n)$

• Complexité temporelle : $O(n^3)$
• Complexité spatiale en entrée : $O(2*n^2)$ pour A et B
• Complexité spatiale auxiliaire : $O(n^2)$, on crée une matrice de plus en mémoire
• Donc la complexité spatiale totale est bornée par : $O(n^2)$

• Complexité temporelle : $O(n.log(n))$. Complexité moins triviale. Il faut bien dérouler des exemples avec 8 valeurs dans le tableau (et en discuter par exemple au tableau). À Chaque appel récursif, les tableaux sont divisés en deux et stockés dans un nouveau tableau (nécessitant une complexité temporelle équivalente au nombre d’éléments dans le tableau). Ainsi à chaque niveau de divisions (2 au début, puis 4, puis 8, etc), nous recopions complètement le tableau initial en sous-tableaux indépendants (coûtant O(n) en complexité temporelle). Donc comme il y a O(log(n)) niveaux dû aux divisions, et qu’il faut O(n) à chaque niveau afin de tout parcourir/recopier. La complexité temporelle finale est O(n)*O(log(n))= O(nlog(n)). Cette méthode est connue sous le nom de “diviser pour reigner”.
• Complexité spatiale en entrée : $O(n)$ pour la liste T
• Complexité spatiale auxiliaire : $O(n + log(n))$. Cette complexité, à la différence de la temporelle, doit prendre en compte l’espace maximum utilisé à n’importe quel moment de l’algorithme et non une somme de l’espace mémoire utilisé. L’utilisation d’une pile d’appels coute $O(log(n))$ (diviser l’espace). Pour ce qui est du stockage des tableaux recréés à chaque appel récursif, il faut analyser ce qui se passe lors d’un empilement d’appels jusq’au dépilement. Quand on empile les appels, au premier appel on stocke $n/2$ éléments, puis $n/4$ éléments, puis $n/8$ etc, jusqu’à $1$ élément. Donc au maximum d’une séquence d’empilement ($log(n)$ appels), on a $n/2 + n/4 + n/8 +n/16 + \ldots + 1 = n$. Or on a aussi le tableau de départ (complexité spatiale en entrée), donc à n’importe quel instant on stoke au maximum $n$ éléments. Quand on dépile, on ne stoke plus les éléments, puis on re-emplile les branches suivantes donnant à nouveau au maximum $n$ éléments stockés en plus du tableau de départ.
• Ainsi, la complexité spatiale totale est bornée par : $O(n)$

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

Dans ce cas, la complexité temporelle est réduite à $O(2^{\log_{2}(n)})$, soit $O(n)$, car on ne recopie plus les tableaux à chaque appel récursif. La complexité spatiale auxiliaire est réduite à $O(\log_2(n))$, car on ne stocke plus les tableaux intermédiaires, mais seulement la pile d’appels récursifs.

• Complexité temporelle : $O(2^n)$, car 2 appels récursifs par élément du tableau
• Complexité spatiale en entrée : $O(n)$ pour la liste T
• Complexité spatiale auxiliaire : $O(n)$, car la profondeur de la pile d’appels récursive donne O(n) en mémoire auxiliaire. Rien n’est stocké ici, on affiche seulement.
• Donc complexité spatiale totale : $O(n)$

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

Pour le cas où nous stockons les solutions, la mémoire auxiliaire reste $O(n)$ pour la pile d’appels récursive, mais la mémoire totale stocke $O(2^n)$ sommes dans une liste.

• Donc la nouvelle complexité spatiale totale est bornée par : $O(2^n)$

1. L’algorithme fct5 affiche sur chaque ligne l’indice “1 1”, “1 2”, “1 3”, “2 1”, “2 2”, “2 3”, etc pour i allant de 1 à 3 et j allant de 1 à 2. L’algorithme passe i en entier avant d’incrémenter j. La complexité temporelle est de $O(n^2)$ et la spatiale de $O(n\times m)$ (la taille de la chaine de caractères).

Dans cette solution, toutes les opérations, à l’exception des appels récursifs, sont en $O(1)$, et la complexité temporelle dans le pire des cas est déterminée par le nombre d’appels récursifs engendrés.

• Si $i>0$, déterminer la valeur de $u(i)$ va nécessiter 3 appels récursifs à $u(i-1)$.
• Si $i>1$, chacun des 3 appels à $u(i-1)$ va engendrer 3 appels à $u(i-2)$, soit 9 appels à $u(i-2)$.
• Si $i>2$, ces 9 appels à $u(i-2)$ vont engendrer à leur tour 3 appels chacun à $u(i-3)$, soit un total de 27 appels à $u(i-3)$.
• De manière imaginée, les appels récursifs forment un $u(i)$ arbre ternaire de hauteur $i+1$.

Le nombre total d’appels récursifs engendrés est de $3^1+3^2+3^3+\ldots+3^i$ et donc $(3^{i+1}-1)/2-1$. La complexité temporelle dans le pire des cas est donc en $O(3^i)$.

2. Voici une seconde solution en réduisant la formule :

1def u(i):
2    if i==0 :
3        return 1
4    else :
5        return u(i-1)*(2+u(i-1))

Dans cette solution, toutes les opérations, à l’exception des appels récursifs, sont en $O(1)$, et la complexité temporelle dans le pire des cas est déterminée par le nombre d’appels récursifs engendrés.

• Si $i>0$, déterminer la valeur de $u(i)$ va nécessiter 2 appels récursifs à $u(i-1)$.
• Si $i>1$, chacun des 2 appels à $u(i-1)$ va engendrer 2 appels à $u(i-2)$, soit 4 appels à $u(i-2)$.
• Si $i>2$, ces 4 appels à $u(i-2)$ vont engendrer à leur tour 2 appels chacun à $u(i-3)$, soit un total de 8 appels à $u(i-3)$.

De manière imaginée, les appels récursifs forment un arbre binaire de hauteur $i+1$.

Le nombre total d’appels récursifs engendrés est de $2^1+2^2+2^3+\ldots+2^i$ et donc $(2^{i+1}-2)$. La complexité temporelle dans le pire des cas est donc en $O(2^i)$.

3. Voici une troisième solution en stockant la solution avant les calculs :

1def u(i):
2    if i==0 :
3        return 1
4    else :
5        appel = u(i-1)
6        return appel*(2+appel)

Chaque appel à $u(i-1)$ retournera la même valeur, donc plutot que de calculer plusieurs fois cette valeur, autant ne la calculer qu’une fois et mémoriser ce résultat pour s’en resservir. C’est l’idée de cette 3ème version. Comme dans les précédentes versions toutes les opérations, à l’exception des appels récursifs, sont en $O(1)$, et la complexité temporelle dans le pire des cas est déterminée par le nombre d’appels récursifs engendrés. Cependant cette fois les appels récursifs forment une chaine de longueur puisque $u(i)$ ne fait qu’un seul appel à $u(i-1)$, lequel ne fait qu’un seul appel à $u(i-2)$, etc.

Il y a donc au total $i$ appels récursifs et la complexité temporelle dans le pire des cas est donc en $O(i)$.

La méthode fct6 trie les éléments du tableau t dans l’ordre croissant. Il a deux boucles prenant chacune dans le pire des cas $n-1$ pas de boucle. Donc complexité temporelle égale à $O(n^2)$. Pour la complexité spatiale, seule celle du tableau en entrée compte et vaut $O(n)$.

Dans le cas d’un tableau déjà trié, aucune permutation n’a lieu mais on fait quand même $O(n^2)$ pas de boucles. Si dans le pire cas (tableau dans l’ordre décroissant) $n-1$ pas de boucles sur i sont nécessaires pour qu’entre autres le plus petit élément (le dernier du tableau) arrive en t[0]. Généralement, moins de pas de boucles sur i sont nécessaires.

En effet, si pour toutes les valeurs de j aucune permutation n’a lieu c’est que le tableau est trié dans l’ordre croissant et on peut donc s’arrêter. C’est le principe de l’amélioration ci-dessous :

 1def fct5_tri_a_bulles(t : list[int]):
 2    n = len(t)
 3    permut = true
 4    while permut :
 5        permut = false
 6        for j in range(n - 1):
 7            if t[j] > t[j + 1]:
 8                temp = t[j]
 9                t[j] = t[j + 1]
10                t[j + 1] = temp
11                permut = true
12  

Cette modification ne change bien évidemment pas la complexité dans le pire des cas, mais en pratique et en moyenne on est meilleur.

On peut remarquer également que dans la version basique, le pas de boucle avec $i=0$ amène forcément le plus grand élément du tableau en $t[n-1]$, que le deuxième pas de boucle ($i=1$) amène le second plus grand élément en $t[n-2]$, … et la boucle interne sur j peut donc s’arrêter à $n-2-i$ puisque les i dernier éléments du tableau sont déjà à leur place.

Si l’on tient compte de cette remarque l’algorithme devient :

 1def fct5_tri_a_bulles2(t : list[int]):
 2    n = len(t)
 3    permut = true
 4    bien_places = 0
 5    while permut :
 6        permut = false
 7        for j in range(n - 2 - bien_places):
 8            if t[j] > t[j + 1]:
 9                temp = t[j]
10                t[j] = t[j + 1]
11                t[j + 1] = temp
12                permut = true
13        bien_places += 1 # t[n-1-bienPlaces] est assurément bien placé
14  

La complexité dans le pire des cas est en $O((n-1)+(n-2)+(n-3)+\ldots+1)=O(n*(n-1)/2)=O(n^2)$. Elle demeure donc inchangée mais là encore on gagne en temps en moyenne en évitant de tester des valeurs qui sont déjà à leur place. Il est important de voir que l’optimisation d’un algorithme en pratique ne change pas toujours les complexités dans le pire des cas.